13763번 - Dropped Water Bottle 다국어

Tramper Joe is on a multi-day tramping trip. While he is wading across a river, his empty water bottle falls from his pack and starts bobbing off downstream. Joe watches it for some time, wondering if it’s worth his while to chase after it. He eventually decides it is worthwhile so he returns to the left bank of the river, puts his pack down and starts to run downstream after the bottle. It has taken him 2 minutes to decide to pursue the bottle and get to the left bank. The bottle is now 60 metres downstream since the river is flowing at a steady 0.5 metres/second.

On the left bank of the river, Joe can run at a steady speed of 2 metres/second but there are intermittent extended obstacles such as cliff faces right beside the river. However, when he meets an obstacle, he must cross to the right bank where the terrain is rougher and he can run at only 1 metre/second. Crossing the river, which he always does on a line perpendicular to the river, takes 40 seconds. The right bank also has intermittent obstacles at which he must cross back again to the left bank.

If Joe gets to a point where there are obstacles on both banks of the river at the same point, Joe must give up and forfeit his water bottle. However, if an obstacle on one bank starts at the point where an obstacle on the opposite bank finishes, Joe is deemed able to cross from the first bank to the second, resuming his downstream run at exactly the same distance downstream as where the second obstacle finished. If both banks are clear, Joe must decide whether to stay on whatever side he is currently or to wade across the river and continue on the other side.

When Joe has overhauled the bottle by a sufficient amount, he wades into the centre of the river, which takes 20 seconds, and picks up his bottle.

Compute the minimum time for Joe to pick up his water bottle (if possible).

The input will contain a single test case.

The first line contains two integers n_l (0 ≤ n_l ≤ 2 000) and n_r (0 ≤ n_r ≤ 2 000), the number of obstacles on the left bank and the right bank, respectively. The next n_l lines each contain two integers d_i (0 < d_i ≤ 6 000) and l_i (0 < l_i ≤ 6 000), which are the distance downstream from where the bottle was dropped to the ith left-bank obstacle and the length of that obstacle respectively, both in metres. The following n_r lines similarly define the positions and lengths of all right-bank obstacles. On each bank, the obstacles will be given in increasing order based on their d_i value and do not overlap, though they may touch.

Output the minimum time in seconds for Joe to reach his water bottle from when he starts running or the word IMPOSSIBLE if he cannot retrieve his bottle. Output will be considered correct if it is within 10⁻³ of the true answer.