Hurdles of 110m


Time Limit: 2 Seconds      Memory Limit: 65536 KB

In the year 2008, the 29th Olympic Games will be held in Beijing. This will signify the prosperity of China and Beijing Olympics is to be a festival for people all over the world as well.

Liu Xiang is one of the famous Olympic athletes in China. In 2002 Liu broke Renaldo Nehemiah's 24-year-old world junior record for the 110m hurdles. At the 2004 Athens Olympics Games, he won the gold medal in the end. Although he was not considered as a favorite for the gold, in the final, Liu's technique was nearly perfect as he barely touched the sixth hurdle and cleared all of the others cleanly. He powered to a victory of almost three meters. In doing so, he tied the 11-year-old world record of 12.91 seconds. Liu was the first Chinese man to win an Olympic gold medal in track and field. Only 21 years old at the time of his victory, Liu vowed to defend his title when the Olympics come to Beijing in 2008.

In the 110m hurdle competition, the track was divided into N parts by the hurdle. In each part, the player has to run in the same speed; otherwise he may hit the hurdle. In fact, there are 3 modes to choose in each part for an athlete -- Fast Mode, Normal Mode and Slow Mode. Fast Mode costs the player T1 time to pass the part. However, he cannot always use this mode in all parts, because he needs to consume F1 force at the same time. If he doesn't have enough force, he cannot run in the part at the Fast Mode. Normal Mode costs the player T2 time for the part. And at this mode, the player's force will remain unchanged. Slow Mode costs the player T3 time to pass the part. Meanwhile, the player will earn F2 force as compensation. The maximal force of a player is M. If he already has M force, he cannot earn any more force. At the beginning of the competition, the player has the maximal force.

The input of this problem is detail data for Liu Xiang. Your task is to help him to choose proper mode in each part to finish the competition in the shortest time.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 50) which is the number of test cases. And it will be followed by T consecutive test cases.

Each test case begins with two positive integers N and M. And following N lines denote the data for the N parts. Each line has five positive integers T1 T2 T3 F1 F2. All the integers in this problem are less than or equal to 110.

Output

Results should be directed to standard output. The output of each test case should be a single integer in one line, which is the shortest time that Liu Xiang can finish the competition.

Sample Input

2
1 10
1 2 3 10 10
4 10
1 2 3 10 10
1 10 10 10 10
1 1 2 10 10
1 10 10 10 10

Sample Output

1
6

Hint

For the second sample test case, Liu Xiang should run with the sequence of Normal Mode, Fast Mode, Slow Mode and Fast Mode

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t,n,m,ans;
int t1[],t2[],t3[],f1[],f2[];
int dp[][];//dp[i][j]表示第i个障碍,还剩j的能力时最短是时间
int main()
{
while(~scanf("%d",&t))
{
for(;t>;t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d%d%d%d%d",&t1[i],&t2[i],&t3[i],&f1[i],&f2[i]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
dp[i][j]=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
/*
dp[i][j]=dp[i-1][j]+t2[i];
if (j+f1[i]<=m) dp[i][j]=min(dp[i][j],dp[i-1][j+f1[i]]+t1[i]);
if(j>=f2[i]) dp[i][j]=min(dp[i][j],dp[i-1][j-f2[i]]+t3[i]);
//想了半天,突然想到,这样写,让选用三方案后能量超过m的情况被忽略了。
*/
dp[i][j]=min(dp[i][j],dp[i-][j]+t2[i]);
if (j>=f1[i]) dp[i][j-f1[i]]=min(dp[i][j-f1[i]],dp[i-][j]+t1[i]);
dp[i][min(j+f2[i],m)]=min(dp[i][min(j+f2[i],m)],dp[i-][j]+t3[i]);
}
/* for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
printf("%d ",dp[i][j]);
printf("\n");
}*/
ans=;
for(int i=;i<=m;i++)
ans=min(ans,dp[n][i]);
printf("%d\n",ans);
}
}
return ;
}

最新文章

  1. JQuery------判断拥有某个class或id的div是否存在
  2. PHP(1)——学习之前做点啥准备
  3. In App Purchase Statuses
  4. python学习小结9:面向对象
  5. Google 多源码管理工具 gclient
  6. Ajax数据格式,html,xml,json
  7. (转)Newtonsoft.Json序列化和反序列
  8. weblogic启动时报错 java.lang.OutOfMemoryError: PermGen space
  9. ASP.NET MVC 音乐商店 - 目录
  10. poj 3414 Pots (bfs+线索)
  11. 打印机服务器搭建 -cups
  12. Jenkins具体安装与构建部署使用教程
  13. Jquery实现选项卡效果
  14. Hadoop生态组件Hive,Sqoop安装及Sqoop从HDFS/hive抽取数据到关系型数据库Mysql
  15. graph engine
  16. ASP.NET页面之间传值的方式之Server.Transfer(个人整理)
  17. 浅析JavaScript之数组
  18. Syncrhonized 和 Lock的区别和使用
  19. Day 08 文件操作模式,文件复制,游标
  20. centos6.5编译安装php7

热门文章

  1. Java命令:Jstack
  2. require-ensure
  3. 切换usb口的命令
  4. 前端工程师在实现支付功能的时候能做些什么(V客学院技术分享)?
  5. Rsync结合Inotify 实时同步配置(更新之前繁琐的传输认证)
  6. Python3.x:打包为exe执行文件(window系统)
  7. nginx之proxy、cache、upstream模块学习
  8. 20145211《网络渗透》Adobe阅读器渗透攻击
  9. excel日期插件
  10. git分支合并脚本