Building a Wall
Time limit1sMemory limit128 MB
Given block sizes/costs and two target wall silhouettes for horizontal and vertical placement days, compute the minimum total cost to build the wall over two days.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Greedy, Math
- Solved
- No attempts yet
Problem
Donggyu wants to finish a wall of length L over two days.
A store sells N types of blocks in unlimited quantity. The i-th block costs C_i and has size 1 x 1 x D_i.
On one of the two days, every block is placed horizontally; on the other day, every block is placed vertically. Which day uses which orientation is not fixed.
The wall is built on flat ground of length L. At each point in time, the wall shape is described by a silhouette. A silhouette is the upper boundary of the wall, written as a sequence of coordinates (x_1, y_1), (x_2, y_2), ..., (x_M, y_M).
A silhouette satisfies the following conditions.
Mis even.x_1 = 0andx_M = L.- For every
k,x_{2k-1} < x_{2k}andx_{2k} = x_{2k+1}. - For every
k,y_{2k-1} = y_{2k}.
For example, for a wall of length 7, the silhouette of the left figure is (0, 2), (3, 2), (3, 1), (5, 1), (5, 3), (7, 3), and the silhouette of the right figure is (0, 4), (2, 4), (2, 6), (7, 6).
Given the block information, the silhouette after the first day, and the silhouette after the second day, find the minimum total cost needed to complete the wall after the second day.
Input
The first line contains the wall length L. (2 <= L <= 10^9)
The second line contains the number of block types N. (1 <= N <= 100)
Each of the next N lines contains a block length D and cost C. (2 <= D <= 1,000, 1 <= C <= 1,000,000)
The next line contains the number of points M_1 in the first-day silhouette. (2 <= M_1 <= 100,000, and M_1 is even)
Each of the next M_1 lines contains one coordinate of the first-day silhouette, in order. All coordinates are nonnegative integers.
The next line contains the number of points M_2 in the second-day silhouette. (2 <= M_2 <= 100,000, and M_2 is even)
Each of the next M_2 lines contains one coordinate of the second-day silhouette, in order. All coordinates are nonnegative integers.
The wall height does not exceed 10^9. For every x-coordinate, the first-day wall height is less than or equal to the second-day wall height.
Output
Print the minimum cost required to complete the wall. The input is always such that the wall can be built, and the minimum cost does not exceed 10^18.