lnc的一天有 分钟，在他的日程表里有 项活动。
他一天活动的先后顺序无法更改，但是可以选择是否进行。即若选择进行第 项和第 项活动 ，则第 项活动会在第 项之前进行。 第 项活动会花费他 分钟的时间，进行活动的时间之和不得超过一天的总时间。
特别的是，他很在意每项任务给他带来的具体收益，第 项活动的收益系数为 ，这意味着如果这项活动是在第 个被进行的活动，将会给他带来 的收益，他自然希望一天进行的活动收益最大化。
由于他非常忙，没有时间来安排日程，所以希望你来解决这个问题。
第一行有两个正整数，分别为 和 ，代表一天的时间和活动总数。
第二行包含 个整数，第 个代表 ，即第 个活动进行所需要的时间。
第三行包含 个整数，第 个代表 ，即第 个活动的收益系数。
一个正整数，表示最大化后的活动收益。
样例输入：
10 5 1 2 3 4 5 1 1 1 1 3
样例输出：
12
样例解释：
选择活动 ，总收益为 ，为最大