Description

Xiaoming is moving, and everyone comes to help.

Xiaoming now lives on floor $N$. In total, $K$ people need to carry $M$ large boxes up to floor $N$.

At the start, all $M$ boxes are on floor $1$. After a period of chaotic moving, things got messy. Everyone then realized the chaos was inefficient and agreed on a more efficient method:

• Each person moves at a speed of one floor per minute, either up or down.
• Everyone going up carries exactly one box; everyone going down carries no box.
• Upon reaching floor $N$, a person immediately puts the box down and starts going down. Upon reaching floor $1$, a person immediately picks up a box and starts going up.
• When a person going up meets a person going down on the stairs, the up-going person hands the box to the other person, and both reverse direction simultaneously. That is, the person who was carrying a box upward now goes downward without a box, and the person who was going downward without a box now goes upward carrying the box.

Find the minimum time needed to finish moving all the boxes.

Input Format

The first line contains $N, K, M$, denoting the number of floors, the number of people, and the number of boxes still lying on floor $1$.

The next $K$ lines each contain two integers $A_i, B_i$.

$A_i$ is the current floor of the $i$-th person. $B_i$ is $0$ or $1$: $0$ means the $i$-th person is carrying a box and going up, and $1$ means the $i$-th person is going down without a box.

It is guaranteed that no two people are on the same floor at the same time; anyone on floor $1$ must be going up with a box, and anyone on floor $N$ must be going down without a box.

Output Format

Output a single integer: the time to finish moving all the boxes.

5 2 4
1 0
3 0

20

Hint

• For $30\%$ of the testdata, $K \leq 100$, $M \leq 100$.
• For $60\%$ of the testdata, $K \leq 1000$, $M \leq 10^9$.
• For $100\%$ of the testdata, $N \le 10^9$, $K \le 5 \times 10^5$, $M \le 10^9$.

Translated by ChatGPT 5