Problem Description

In the year 2077, due to nearly depleted resources, Dream City has implemented an extremely strict garbage sorting system. Specifically, Dream City divides garbage into \( n \) categories, each of which can only be placed in specific trash cans. Since Dream City has mastered compression technology, garbage is distinguished only by quantity, not by volume.

You are a resident of Dream City. Outside your community, there are \( n + 1 \) trash cans, numbered \( 1, 2, \cdots, n, n + 1 \).

For the first \( n \) trash cans, they can only accept garbage corresponding to their number and have a certain capacity. Specifically, you will be given a sequence of length \( n \), \( r_1, \cdots, r_n \). The \( i \)-th trash can can only accept the \( i \)-th category of garbage and can hold a maximum of \( r_i \) pieces.

For the last trash can, it can accept all types of garbage and has nearly unlimited capacity. However, for each piece of garbage placed in this trash can, the neighborhood committee will charge you a fee of \( c \).

One day, your home is filled with garbage. After sorting these garbage, you get a sequence of length \( n \), \( a_1, \cdots, a_n \), representing that there are \( a_i \) pieces of the \( i \)-th category of garbage.

You want to know the minimum cost to dispose of all these garbage.

Input Format

There are three lines in total.

The first line contains two integers \( n, c \), representing the number of garbage categories and the fee for placing garbage in the last trash can.

The second line contains \( n \) integers \( r_1, \cdots, r_n \), representing the capacities of the trash cans.

The third line contains \( n \) integers \( a_1, \cdots, a_n \), representing the quantities of each category of garbage.

Output Format

One line containing a single integer, representing the minimum cost.

Sample Input and Output

Sample Input #1

2 7
4 3
7 9

Sample Output #1

63

Sample Input #2

2 10000
100 100
3 7

Sample Output #2

0

Notes/Hints

Sample Explanation

Sample Group #1: In the optimal scenario, you need to place \( 9 \) pieces of garbage in the last trash can, with a cost of \( 7 \times 9 = 63 \).

Sample Group #2: In the optimal scenario, you do not need to place any garbage in the last trash can, with a cost of \( 0 \).

Data Range and Constraints

For the first \( 20\% \) of the data, it is guaranteed that \( n = 2 \).

For the first \( 60\% \) of the data, it is guaranteed that \( n, a_i, c \leq 10^3 \).

For another \( 10\% \) of the data, it is guaranteed that \( c = 0 \).

For another \( 10\% \) of the data, it is guaranteed that \( r_i \geq a_i \).

For \( 100\% \) of the data, it is guaranteed that \( 2 \leq n \leq 10^6, 0 \leq r_i, a_i, c \leq 10^6 \).

见题面 Input 部分

见题面 Output 部分