P2339 [USACO04OPEN] Turning in Homework G

Bessie has $C$ assignments to turn in, after which she will take the bus home with her classmates. All teachers’ classrooms are arranged along a corridor of length $H$. They accept assignments only after class, and turning them in takes no time. Bessie starts at position $0$. You are given each classroom’s position and the position of the corridor exit (bus stop). For every unit of distance she walks, she spends 1 minute. Compute the earliest time by which she can finish turning in all assignments and reach the exit.

The first line contains three integers $C$, $H$, and $B$ ($1 \le C \le 1000, 1 \le H \le 1000, 0 \le B \le H$). Lines $2$ through $C+1$: on the $(i+1)$-th line, there are two integers $X_i$ and $T_i$ ($0 \le X_i \le H, 0 \le T_i \le 10^4$). $B$ denotes the position of the corridor exit. $X_i$ is the position where the $i$-th assignment must be turned in. $T_i$ is the dismissal time of the teacher for that subject (the one who accepts this assignment) at that position.

Output a single integer, the minimum time for Bessie to finish turning in all assignments and reach the exit.

In the sample, she walks to coordinate 8, turns in one assignment at minute 9, waits until minute 12 to turn in another, then walks to coordinate 4 to turn in, and finally goes to coordinate 3 to turn in the last assignment, which is also the bus stop location, for a total of 22 minutes. Translated by ChatGPT 5