Back To School '17: Wet Mud

View as PDF
Submit solution
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 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 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 inches. Given the 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, M and 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 lines will contain two integers, p_i and t_i, the p^\text{th} inch of mud will dry after t_i minutes.

Constraints

0 \le M \le N

0 \le J \le N+1

1 \le p_i \le N

1 \le t_i \le 10^6

Subtask 1 [20%]

1 \le N \le 1000

Subtask 2 [80%]

1 \le N \le 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

4 2 3
4 1
3 4

Sample Output 1

4

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

4 4 1
3 2
4 5
1 1
2 3

Sample Output 2

5

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

3 1 1
1 2

Sample Output 3

-1

Comments