codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

241A.md (2104B)


      1 Source: https://codeforces.com/problemset/problem/241/A
      2 
      3 A. Old Peykan
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 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.
     22 
     23 The Old Peykan travels 1 kilometer in 1 hour and consumes 1 liter of fuel during this time.
     24 
     25 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.
     26 
     27 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.
     28 
     29 Find the minimum time the Old Peykan needs to reach city *c**n*.
     30 
     31 Input
     32 
     33 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.
     34 
     35 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).
     36 
     37 Output
     38 
     39 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.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4 6  
     47 1 2 5 2  
     48 2 3 3 4
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 10
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 2 3  
     61 5 6  
     62 5 5
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 14
     69 ```
     70 
     71 Note
     72 
     73 In the second sample above, the Old Peykan stays in *c*1 for 3 hours.