P1798 Xiaoming Moves House

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.

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 a single integer: the time to finish moving all the boxes.

- 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