10208번 - Milo of Croton and the Calf 다국어

Milo of Croton was a six-time Olympic champion in wrestling famed for his strength. He supposedly saved Pythagoras’s life by holding up the ceiling of a collapsing building until Pythagoras was safe. He in part acquired his strength by a training regimen of carrying a calf around the village once a day for a long time, until it was a full-grown bull.4

In this problem, we will evaluate Milo’s training regimen a little more carefully. When you carry a young bull around the village, there are two effects: you’ll be sore for the next few days (and able to lift less weight), and you’ll build up more muscle for the future, allowing you to lift more weight in the future. For each day (equivalently, weight of the calf), you will be given two numbers: a permanent strength increase, which will kick in 3 days after the exercise, and a soreness penalty, which will be in effect the next 2 days after the exercise. Both permanent strength increase and soreness penalties are cumulative, i.e., if Milo exercises for two days in a row, for the next day after that, he will be sore from both, and the second day after, he will be just sore from the second exercise (while gaining the strength from the first).

You will be told how much the calf weighed the first day, how much Milo could lift on the first day, how many days Milo wants to exercise, and what the exercise effects are for carrying the calf at the different weights. When Milo’s ability to lift equals the weight of the calf, he will be successful in lifting it, but not when it is strictly less. Milo exercises every day, and the calf gains one pound every day. Your goal is to determine if Milo can successfully finish his exercise regimen, and if not, on what day he first fails.

The first line is the number K of input data sets, followed by the K data sets, each of the following form:

The first line contains three integers w, c, d, separated by a space. 0 ≤ w ≤ 1000 is the weight that Milo can lift on day 1. 0 ≤ c ≤ 1000 is the weight of the calf on day 1. 1 ≤ d ≤ 100 is the number of days that Milo is planning to exercise.

This is followed by d lines. Each line i = 1, . . . , d describes the effect of carrying the calf around the village when it weighs c + i − 1, i.e., on day i. It consists of two integers g_i, s_i. 0 ≤ g_i ≤ 1000 is the permanent strength gain from carrying the calf, which kicks in at day i + 3. 0 ≤ s_i ≤ 100 is the soreness penalty from carrying the calf, which hurts him on days i + 1 and i + 2.

For each data set, output “Data Set x:” on a line by itself, where x is its number.

If Milo can finish his entire regimen, then output “Completed successfully.” Otherwise, output the first day on which Milo cannot carry the calf any more.

Each data set should be followed by a blank line.