403187: GYM101063 E Mars Explorer

In previous Mars missions the surface has been explored and mapped. A number of spots have been found where GEMA wants to collect interesting rock samples. GEMA is a bit on a tight budget, but luckily they recovered the old NASA Mars rover, and were able to repurpose it for this.

The rover is quite old and has very limited power. On the hilly Mars landscape it is limited in how much weight it can carry along, depending on how steep a slope it has to take uphill. You are tasked to decide which rock samples to collect in one single haul to maximize the total weight of rock samples.

To simplify matters, only a 1D section of the Mars surface (along the x coordinate) is given with height (y coordinate) along the that section. The base where the rover starts and has to return is at x = 0. The rover can only climb uphill if the slope s > 0 satisfies s ≤ P / M where P is the power of the rover, and M is its total weight, including any rocks already collected.

The first line of the input contains four integers: N (2 ≤ N ≤ 100), the number of points describing the landscape, R (1 ≤ R ≤ 100), the number of rock samples, m (1 ≤ m ≤ 1 000), the weight of the rover, and P (1 ≤ P ≤ 500), the power of the rover. The next N lines each contain two integers x_i, y_i with 0 ≤ x_i, y_i ≤ 1 000. The sequence of x_i is strictly increasing and x₁ = 0. The landscape is given by straight lines connecting sequential points (x_i, y_i). The next R lines each contain two integers X_i, m_i with 1 ≤ X_i ≤ x_N the x-coordinate of the rock sample and 1 ≤ m_i ≤ 10⁵ its weight.

Print a single line containing an integer: the maximum weight of the rock samples that can be collected.

3 2 50 20
0 5
20 5
30 10
4 42
28 10

42

4 3 50 500
0 0
20 100
70 50
100 0
10 10000
21 445
83 10

10445

In the first sample test case the rover cannot reach all of the surface, since the slope from x₂ to x₃ is too steep. In the second sample the rover can reach the whole surface, but can only climb uphill from x₃ to x₂ with either one of the rocks with weight 445 or 10.