Gautam Buddha University is organising a car racing competition "GBU F1 Racers". Each contestant has to build a car on his own and then drive it on the day of the competition. The winner of the competition gets a Ferrari sports car.

The rules of the competition are as follows:
1. There will be 'n' checkpoints in the race.
2. All the checkpoints are located on a straight line.
3. The checkpoints are denoted from left to right as c₁, c₂,..., c_n.
4. Each contestant has to travel from checkpoint c₁ to c_n using roads.
5. There are (n-1) one-way roads, the i-th road goes from checkpoint c_i to checkpoint c_i+1 and is d_i kilometres long.
6. Each checkpoint, except for the last one, has a supply of s_i liters of fuel which immediately transfers to every car that either passes the checkpoint or stays at the checkpoint for k minutes, i.e., the supply refreshes instantly k minutes after it transfers.
7. Each contestant may stay at a checkpoint for 'multiple of k' minutes and fill its fuel tank many times.
8. Initially (at time zero), the car is at checkpoint c₁ and s₁ litres of fuel is transferred to it's empty tank from c₁'s supply.
9. The car is disqualified if its fuel tank gets emptied strictly between two checkpoints.

Raghav Singh, a student of B.Tech (Mechanical), has passion for sports cars and wants to win this race at any cost. He works really hard to build a powerful car. The special thing about his car is that its fuel tank capacity is unlimited.

His car travels 1 kilometres in 1 minute and consumes 1 litre of fuel during this time.

As the day of the competition is coming soon, he wants make a software program to find the minimum time his car needs to reach the checkpoint c_n. Raghav is not good in programming, therefore he needs your help to find the minimum time his car will need to reach the checkpoint c_n.

Input:
The first line of the input contains two space-separated integers m and k. The value m specifies the number of roads which is equal to n-1.
The next line contains m space-separated integers d₁,d₂,..., d_m and the following line contains m space-separated integers s₁,s₂,..., s_m.

Output:
In the only line of the output print a single integer — the minimum time required by the Raghav's car to reach checkpoint c_n from checkpoint c₁.

Constraints:
m>=1
k≤1000
1≤d_i≤1000
1≤s_i≤1000

Example:

Input:
4 6
1 2 5 2
2 3 3 4

Output:
10