题目描述

After sovling Chen's problem Youmu keeps on her way. Now she comes to the Hakurei Shrine.

It didn't go very smoothly, Youmu also solved a problem of Letty. But for now, she seems to arrive at the final destination.

The miko of the Hakurei Shrine, Reimu Hakurei is one of the leader of Gensoukyo, so if she can help bring the spring back to the Netherworld to Yuyuko. Then whole mission will be done.

But now, for some kind of reason, Reimu is poor right now and have to make some money.

There's a job for Reimu, just needs her purity(jiecao) to exchange money.

The job continues for $N$ days, every day Reimu can sell some amount of her purity to exchange for some money, and have some rules below:

1. Do nothing, if the president purity of Reimu can't afford to the $i-th$ day job, or she just with the intention of doing nothing.

2. Exchange her $a[i]$ purity for the exact $b[i]$ amount of money.

3. Exchange her $a[i]$ purity for the $2\ imes b[i]$ amount of the money, but if she chooses this, tommorow the amount of the money $b[i+1]$ will be shrunk into $\\lfloor\\frac{1}{2}\\rfloor$ and she can only use rules 1,2 tommorow.

4. Exchange her $a[i]$ purity for the $3\ imes b[i]$ amount of the money, but if she chooses this, the day after tommorow the amount of the money $b[i+2]$ will be shrunk into $\\lfloor\\frac{1}{3}\\rfloor$, and she can only use rules 1,2 the day after tommorow and she can't exchange anything tommorow.

Now Reimu has already got the list of the job, with the expected purity needed for each day and how much money can be exchanged.

But as greedy as Reimu is, she wants to get as much money as posiible with her mearly little purity. So she comes to Youmu to help her make a plan.

Youmu does it perfectly, so can you help Reimu,too?

picture: Reimu with the Hakurei Shrine

输入格式

The first line of input contains two positive integers $N,M (1\\le N,M\\le 10000)$ indicating the number of the days of the job, and the initial purity Reimu has.

Then follows $N$ integers $a[i]( 1\\le a[i]\\le10000)$ indicating the purity needed each day.

Then follows $N$ integers $b[i](0\\le b[i]\\le 10^9)$ indicating the expected amount of money can be exchanged each day.

输出格式

One positive integer, the amount of money Reimu can obtain with the price of her purity, if she makes the plan optimally.

样例

3 3 
1 1 1 
1 2 3 

12

3 2 
1 1 1 
5 2 3

19

3 1 
5 5 5 
5 5 5

0

提示

In the first test case, Reimu can get $3\ imes b[i]$ at day 3. Then the total money Reimu can get is $1+2+3\ imes3=12$.

Please notice that, though Reimu get $3\ imes b[i]$ at day 3 and there's no day 5, it is also legal.

In the second test case, Reimu can get $2\ imes b[i]$ at day 1. Then she does nothing at day 2 and she can get $3\ imes b[i]$ at day 3. So, the total of money Reimu can get is $5\ imes2+0+3\ imes3=19$

In the third test case, Reimu can exchange nothing, because of her purity is too little.