OpenJudge

H:运石头

总时间限制:
1000ms
内存限制:
65535kB
描述

路上摆着一排石头,石头大小不一,而小明负责保运这些石头。小明决定把这些石头叠在一起,然后一起搬走。为了在搬运的时候石头堆不倒下,所以一块石头上不能放比它还大的石头。石头一共有N(1<=N<=20)块,每块石头有自身的重量ai和 小明搬起这块石头需要花费的时间ti秒钟(1<=i<=N)。但是时间有限,小明一共只有T(1<=T<=2000)秒钟把石头堆起来,所以有时必须舍弃一些石头。于是小明打算从左边一直走到右边,不回头的捡起部分石头,请问小明最多能捡起的石头的总重量是多少?

输入
每组输入三排
第一排两个数: N 和 T
第二排N个数,分别代表a1,a2,a3......aN(1<=ai<=100)
第三排N个数,分别代表t1,t2,t3......tN(1<=ti<=100)
输出
每次输出一排,最大的总重量。
样例输入
4 10
4 5 3 3
2 4 2 5
3 4
3 2 1
3 2 1
样例输出
10
4
来源
刘清华
全局题号
13301
提交次数
6
尝试人数
2
通过人数
1