Description

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.

Input Format

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 Format

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

4 10 3
8 9
4 21
3 16
8 12

22

Hint

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