Problem Old Peykan

http://codeforces.com/problemset/problem/241/A

A. Old Peykan

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are n cities in the country where the Old Peykan lives. These cities are located on a straight line, we'll denote them from left to right as c₁, c₂, ..., c_n. The Old Peykan wants to travel from city c₁ to c_nusing roads. There are (n - 1) one way roads, the i-th road goes from city c_i to city c_i + 1 and is d_ikilometers long.

The Old Peykan travels 1 kilometer in 1 hour and consumes 1 liter of fuel during this time.

Each city c_i (except for the last city c_n) has a supply of s_i liters of fuel which immediately transfers to the Old Peykan if it passes the city or stays in it. This supply refreshes instantly k hours after it transfers. The Old Peykan can stay in a city for a while and fill its fuel tank many times.

Initially (at time zero) the Old Peykan is at city c₁ and s₁ liters of fuel is transferred to it's empty tank fromc₁'s supply. The Old Peykan's fuel tank capacity is unlimited. Old Peykan can not continue its travel if its tank is emptied strictly between two cities.

Find the minimum time the Old Peykan needs to reach city c_n.

Input

The first line of the input contains two space-separated integers m and k (1 ≤ m, k ≤ 1000). The valuem specifies the number of roads between cities which is equal to n - 1.

The next line contains m space-separated integers d₁, d₂, ..., d_m (1 ≤ d_i ≤ 1000) and the following line contains m space-separated integers s₁, s₂, ..., s_m (1 ≤ s_i ≤ 1000).

Output

In the only line of the output print a single integer — the minimum time required for The Old Peykan to reach city c_n from city c₁.

Sample test(s)

input

4 6
1 2 5 2
2 3 3 4

output

10

input

2 3
5 6
5 5

output

14

Note

In the second sample above, the Old Peykan stays in c₁ for 3 hours.

Algorithm: brute-force.
Giả sử khi đi đến i, lượng xăng trong bình là temp, khoảng cách từ thành phố i đến thành phố i + 1 là d[i], lượng xăng được nạp khi đến i là s[i]. có hai trường hợp:
TH1: temp + s[i] < d[i]. Không đủ xăng để đi đến thành phố i + 1, ta có thể đứng đợi k*m (m lần) giờ để được nạp lại m * s[i] lít xăng. Tuy nhiên s[i] của trạm i chưa chắc là tối ưu nếu lượng xăng nạp ở trạm j ( j<i) mà s[j] > s[i] thì ta nên đứng ở trạm thứ j để nạp xăng. Như thế lượng xăng còn lại trong bình khi ta đi tiếp đến thành phố i + 1 sẽ nhiều hơn.
TH2: temp + s[i] > d[i] , đương nhiên ta đủ xăng để đi tiếp.

code:

#include<iostream>
#include<cstdio>

#define Off true

using namespace std;
int N,K,d[1005],s[1005];
int res = 0,m = 0;
int main()
{
if(Off)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
cin >> N >> K;
int temp = 0;
for(int i=0;i<N;i++) scanf("%d",&d[i]);
for(int i=0;i<N;i++) scanf("%d",&s[i]);
for(int i=0;i<N;i++)
{
temp += s[i] - d[i];
res += d[i];
if(i==0 || m < s[i]) m = s[i];
while(temp < 0)
{
res += K;
temp += m;
}
}
cout << res << endl;
return 0;
}