codeforces-scrape

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

175C.md (2563B)


      1 Source: https://codeforces.com/problemset/problem/175/C
      2 
      3 C. Geometry Horse
      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 Vasya plays the Geometry Horse.
     22 
     23 The game goal is to destroy geometric figures of the game world. A certain number of points is given for destroying each figure depending on the figure type and the current factor value.
     24 
     25 There are *n* types of geometric figures. The number of figures of type *k**i* and figure cost *c**i* is known for each figure type. A player gets *c**i*·*f*  points for destroying one figure of type *i*, where *f* is the current factor. The factor value can be an integer number from 1 to *t* + 1, inclusive. At the beginning of the game the factor value is equal to 1. The factor is set to *i* + 1 after destruction of *p**i* (1 ≤ *i* ≤ *t*) figures, so the (*p**i* + 1)-th figure to be destroyed is considered with factor equal to *i* + 1.
     26 
     27 Your task is to determine the maximum number of points Vasya can get after he destroys all figures. Take into account that Vasya is so tough that he can destroy figures in any order chosen by him.
     28 
     29 Input
     30 
     31 The first line contains the only integer number *n* (1 ≤ *n* ≤ 100) — the number of figure types.
     32 
     33 Each of the following *n* lines contains two integer numbers *k**i* and *c**i* (1 ≤ *k**i* ≤ 109, 0 ≤ *c**i* ≤ 1000), separated with space — the number of figures of the *i*-th type and the cost of one *i*-type figure, correspondingly.
     34 
     35 The next line contains the only integer number *t* (1 ≤ *t* ≤ 100) — the number that describe the factor's changes.
     36 
     37 The next line contains *t* integer numbers *p**i* (1 ≤ *p*1 < *p*2 < ... < *p**t* ≤ 1012), separated with spaces.
     38 
     39 Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.
     40 
     41 Output
     42 
     43 Print the only number — the maximum number of points Vasya can get.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 1  
     51 5 10  
     52 2  
     53 3 6
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 70
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 2  
     66 3 8  
     67 5 10  
     68 1  
     69 20
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 74
     76 ```
     77 
     78 Note
     79 
     80 In the first example Vasya destroys three figures first and gets 3·1·10 = 30 points. Then the factor will become equal to 2 and after destroying the last two figures Vasya will get 2·2·10 = 40 points. As a result Vasya will get 70 points.
     81 
     82 In the second example all 8 figures will be destroyed with factor 1, so Vasya will get (3·8 + 5·10)·1 = 74 points.