codeforces-scrape

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

139B.md (2899B)


      1 Source: https://codeforces.com/problemset/problem/139/B
      2 
      3 B. Wallpaper
      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 Having bought his own apartment, Boris decided to paper the walls in every room. Boris's flat has *n* rooms, each of which has the form of a rectangular parallelepiped. For every room we known its length, width and height of the walls in meters (different rooms can have different dimensions, including height).
     22 
     23 Boris chose *m* types of wallpaper to paper the walls of the rooms with (but it is not necessary to use all the types). Each type of wallpaper is sold in rolls of a fixed length and width (the length, naturally, shows how long the unfolded roll will be). In addition, for each type we know the price of one roll of this type.
     24 
     25 The wallpaper of each type contains strips running along the length of the roll. When gluing the strips must be located strictly vertically (so the roll cannot be rotated, even if the length is less than the width). Besides, a roll can be cut in an arbitrary manner, but the joints of glued pieces should also be vertical. In addition, each room should be papered by only one type of wallpaper. And pieces of the same roll cannot be used to paper different rooms. That is, for each room the rolls are purchased separately. Also, some rolls can be used not completely.
     26 
     27 After buying an apartment Boris is short of cash, so he wants to spend the minimum money on wallpaper. Help him.
     28 
     29 Input
     30 
     31 The first line contains a positive integer *n* (1 ≤ *n* ≤ 500) — the number of rooms in Boris's apartment.
     32 
     33 Each of the next *n* lines contains three space-separated positive integers — the length, width and height of the walls in a given room in meters, respectively.
     34 
     35 The next line contains a positive integer *m* (1 ≤ *m* ≤ 500) — the number of available wallpaper types.
     36 
     37 Each of the following *m* lines contains three space-separated positive integers — the length and width in meters of a given wallpaper and the price of one roll, respectively.
     38 
     39 All numbers in the input data do not exceed 500. It is guaranteed that each room can be papered using these types of wallpaper.
     40 
     41 Output
     42 
     43 Print a single number — the minimum total cost of the rolls.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 1  
     51 5 5 3  
     52 3  
     53 10 1 100  
     54 15 2 320  
     55 3 19 500
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 640
     62 ```
     63 
     64 Note
     65 
     66 Note to the sample:
     67 
     68 The total length of the walls (the perimeter) of the room is 20 m.
     69 
     70 One roll of the first type can be cut into pieces to get three vertical 1 meter wide strips, ergo you need 7 rolls of this type, the price equals 700.
     71 
     72 A roll of the second type can be cut into pieces to get five 2 meter wide strips, we need 2 rolls, the price is 640.
     73 
     74 One roll of the third type can immediately paper 19 meters out of 20, but we cannot use other types and we have to buy a second roll, the price is 1000.