Back To School '17: Wet Mud

View as PDF

Submit solution


Points:10 (partial)
Time limit:2.0s
Memory limit:256M
Author:

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 Specifications

The first line contains 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 amount 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


  • 1
    MackenzieTeam3
     commented on Sept. 9, 2017 edit 2

    How can Denesh jump 0 inches?


    • 19
      Daniel123
       commented on Sept. 10, 2017

      Denesh can't jump

    • -1
      1yangdan
       commented on Sept. 9, 2017

      even a bacteria can jump 0 inch


    • -1
      bawsness
       commented on Sept. 9, 2017

      Why would he jump 0 inches


      • 2
        MackenzieTeam3
         commented on Sept. 9, 2017

        The constraints indicate Denesh can jump greater than or equal to 0 inches. It also indicates that the patch of wet mud can be 0 inches for some reason.


        • -1
          Pleedoh
           commented on Sept. 9, 2017

          No, N is greater than or equal to 1. However, there may not be any patches of mud that dry, as M can be zero.