CSES - Monster Game II
  • Time limit: 1.00 s
  • Memory limit: 512 MB

You are playing a game that consists of nn levels. Each level has a monster. On levels 1,2,,n11,2,\dots,n-1, you can either kill or escape the monster. However, on level nn you must kill the final monster to win the game.

Killing a monster takes sfsf time where ss is the monster's strength and ff is your skill factor. After killing a monster, you get a new skill factor (lower skill factor is better). What is the minimum total time in which you can win the game?

Input

The first input line has two integers nn and xx: the number of levels and your initial skill factor.

The second line has nn integers s1,s2,,sns_1,s_2,\dots,s_n: each monster's strength.

The third line has nn integers f1,f2,,fnf_1,f_2,\dots,f_n: your new skill factor after killing a monster.

Output

Print one integer: the minimum total time to win the game.

Constraints

  • 1n21051 \le n \le 2 \cdot 10^5
  • 1x1061 \le x \le 10^6
  • 1si,fi1061 \le s_i, f_i \le 10^6

Example

Input:

5 100
50 20 30 90 30
60 20 20 10 90

Output:

2600

Explanation: The best way to play is to kill the second and fifth monster.