lnc的一天有 TTT 分钟，在他的日程表里有 nnn 项活动。
他一天活动的先后顺序无法更改，但是可以选择是否进行。即若选择进行第 iii 项和第 jjj 项活动 (i<j)(i<j)(i<j)，则第 iii 项活动会在第 jjj 项之前进行。 第 iii 项活动会花费他 tit_iti 分钟的时间，进行活动的时间之和不得超过一天的总时间。
特别的是，他很在意每项任务给他带来的具体收益，第 iii 项活动的收益系数为 wiw_iwi，这意味着如果这项活动是在第 kkk 个被进行的活动，将会给他带来 k∗wik*w_ik∗wi 的收益，他自然希望一天进行的活动收益最大化。
由于他非常忙，没有时间来安排日程，所以希望你来解决这个问题。
第一行有两个正整数，分别为 TTT 和 nnn ，代表一天的时间和活动总数。
第二行包含 nnn 个整数，第 iii 个代表 tit_iti，即第 iii 个活动进行所需要的时间。
第三行包含 nnn 个整数，第 iii 个代表 wiw_iwi，即第 iii 个活动的收益系数。
一个正整数，表示最大化后的活动收益。
样例输入：
10 5 1 2 3 4 5 1 1 1 1 3
样例输出：
12
1≤n≤181\leq n \leq 181≤n≤18
1≤T,ti,wi≤1091\leq T,t_i,w_i \leq 10^91≤T,ti,wi≤109
样例解释：
选择活动 2,3,52,3,52,3,5，总收益为 1×1+1×2+3×3=121\times 1+1\times 2+3\times 3=121×1+1×2+3×3=12，为最大