401521: GYM100488 H Tony Hawk's Pro Skater

Alex loves the game Tony Hawk's Pro Skater very much. Some tasks in this game oblige the player to perform tricks by pressing certain combinations of buttons and to earn points for that: the more — the better.

Alex has learned how to perform n types of tricks. But to make the game more interesting, its authors provided the following: the reward for every trick decreases while player keeps performing it (but cannot become less than 1). Thus, if player performs the i-th trick for the first time, he earns a_i points, for the second time — points and so on: k-th performance costs points. Performance of the trick of some type doesn't affect the costs of tricks of the other types.

The time in the game is limited so Alex is able to perform only m tricks. What is the maximal number of points he can gain?

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁹) — the number of types of tricks Alex can perform and the number of tricks he has time to perform.

The next line contains n integers a₁, ..., a_n (1 ≤ a_i ≤ 10⁹) — the initial costs of the tricks.

The next line contains n integers b₁, ..., b_n (1 ≤ b_i ≤ 10⁹) — the number of points by which the cost of the corresponding trick reduces at each its performance.

Output a single integer — the maximal number of points which can be gained by performing m tricks.

3 6
9 7 17
1 2 3

67

3 7
9 7 17
2 1 4

68