Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Old Peykan

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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*_{1}, *c*_{2}, ..., *c*_{n}. The Old Peykan wants to travel from city *c*_{1} to *c*_{n} using 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*_{i} kilometers 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*_{1} and *s*_{1} liters of fuel is transferred to it's empty tank from *c*_{1}'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 value *m* specifies the number of roads between cities which is equal to *n* - 1.

The next line contains *m* space-separated integers *d*_{1}, *d*_{2}, ..., *d*_{m} (1 ≤ *d*_{i} ≤ 1000) and the following line contains *m* space-separated integers *s*_{1}, *s*_{2}, ..., *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*_{1}.

Examples

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*_{1} for 3 hours.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 06:25:33 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|