Old Peykan

## 题面 有n个城市，n-1条单向路，第i条路连接城市i和i+1，长度为d[i]。 每个城市(除了第n个)都有s[i]升汽油，每到一个城市就会自动加那么多油，每等k小时即可再加一次油。 有一辆老爷车，1小时走1千米,要用1升油，油箱容量无限，目前在1号城市，要走到n号，至少要多长时间？ ## 输入 第一行：两个整数：m(路的数量),k(等待时间) 第二行：d[1]~d[m] 第三行：s[1]~s[n-1] ## 输出 一个整数，即问题答案。 ## 数据范围 1≤m,k≤1000 1≤d[i],s[i]≤1000 ## 来源 [CF241A](https://codeforces.com/problemset/problem/241/A)

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_{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} $ .

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) $ .

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} $ .

4 6
1 2 5 2
2 3 3 4

10

2 3
5 6
5 5

14

In the second sample above, the Old Peykan stays in $ c_{1} $ for 3 hours.