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 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, 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 inches. Given the 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
Note: It takes no time for Denesh to complete a jump.
The first line contains three integers, , and , 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 lines will contain two integers, and , the inch of mud will dry after minutes.
Subtask 1 [20%]
Subtask 2 [80%]
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
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
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