Back To School '17: Wet Mud

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Daniel123

Problem type

Denesh is walking along a pathway in a forest. He encounters a part of the trail where there is a patch of wet mud that is $N$ $N$ inches long. The trail continues on the other side of the wet mud. Denesh just bought a new pair of shoes so he doesn't want to ruin them by stepping in wet mud, but he is fine with stepping in dry mud. Luckily, $M$ $M$ parts of mud, each being 1 inch in length, will dry at different points in time. No two parts of mud can become dry at the same time.

Denesh can jump as far as $J$ $J$ inches. Given the $M$ $M$ inches of mud that will dry, and the time it takes for them to dry, determine the minimum time it takes Denesh to get to the other side of the trail. If it is impossible for him to get to the other side, print -1.

Note: It takes no time for Denesh to complete a jump.

Input Specification

The first line will contain three integers, $N$ $N$ , $M$ $M$ and $J$ $J$ , the length of the wet mud, the number of parts of wet mud that will become dry, and how far Denesh can jump in inches, respectively.

The next $M$ $M$ lines will contain two integers, $p_i$ $p_{i}$ and $t_i$ $t_{i}$ , the $p^\text{th}$ $p^{th}$ inch of mud will dry after $t_i$ $t_{i}$ minutes.

Constraints

$0 \le M \le N$ $0 \leq M \leq N$

$0 \le J \le N+1$ $0 \leq J \leq N + 1$

$1 \le p_i \le N$ $1 \leq p_{i} \leq N$

$1 \le t_i \le 10^6$ $1 \leq t_{i} \leq 10^{6}$

Subtask 1 [20%]

$1 \le N \le 1000$ $1 \leq N \leq 1000$

Subtask 2 [80%]

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$

Output Specification

Output the minimum number of minutes it will take Denesh to get to the other side of the trail, or -1 if it is impossible.

Sample Input 1

Copy

4 2 3
4 1
3 4

Sample Output 1

Copy

Explanation for Sample Output 1

After 4 minutes, Denesh can get across the wet mud in 2 jumps. First by jumping to the dry mud at the third inch, and then jumping to the other side of the trail.

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

After the first minute, Denesh can jump to the first inch of mud. He then has to wait 3 minutes to jump to the second patch of mud, and then immediately after jumps to the third patch of mud. After the fifth minute, he takes two jumps to the other side of the trail.

Sample Input 3

Copy

3 1 1
1 2

Sample Output 3

Copy

-1

Comments

8

MackenzieTeam3 commented on Sept. 10, 2017, 1:25 a.m. ← edit 2 →

How can Denesh jump 0 inches?

122

Daniel123 commented on Sept. 10, 2017, 4:17 a.m. ← edited →