gbu-f1-racers

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 c1, c2,..., cn.
4. Each contestant has to travel from checkpoint c1 to cn using roads. 
5. There are (n-1) one-way roads, the i-th road goes from checkpoint ci to checkpoint ci+1 and is di kilometres long.
6. Each checkpoint, except for the last one, has a supply of si 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 c1 and s1 litres of fuel is transferred to it's empty tank from c1'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 cn.
Raghav is not good in programming, therefore he needs your help to find the minimum time his car will need to reach the checkpoint cn.  

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 d1,d2,..., dm and the following line contains m space-separated integers s1,s2,..., sm.  

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

Constraints:
m ≥ 1
k≤1000
1≤di≤1000
1≤si≤1000  

Example:  

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

Output:  
10  

SAMPLE INPUT
2 3
5 6
5 5

SAMPLE OUTPUT
14

Source: hackerearth | Difficulty: MEDIUM


Solutions: