Woburn Challenge 2018-19 Round 1 - Senior Division

It's time for Bob to face his biggest fear at H.S. High School: the dreaded gym class rope climb. In this brutal test of strength and endurance, Bob is tasked with ascending part of the way up an infinitely long vertical rope. He begins by grabbing onto the bottom of the rope, at a height of 0, and must reach any height of ~H~ ~(1 \le H \le 1\,000\,000)~ or greater (measured in metres).

To make matters even worse than usual, Alice has pranked Bob by spreading itching powder on some sections of the rope, which he'll need to avoid along the way! She's done so for ~N~ ~(0 \le N \le H - 1)~ sections, the ~i~-th of which covers all heights from ~A_i~ to ~B_i~, inclusive ~(1 \le A_i \le B_i \le H - 1)~. No two sections overlap with one another, even at their endpoints.

Bob's rope-climbing style is… unusual, to say the least, which may come in handy for avoiding Alice's itching powder. At any point, given that he's currently holding onto the rope at some height ~h_1~, he may only perform one of the following two possible actions:

1. Jump upwards by a height of exactly ~J~ ~(1 \le J \le H)~, such that his new height is ~h_2 = h_1 + J~, but only if the rope is not covered in itching powder at height ~h_2~.
2. Drop downwards by any height, such that his new height is any integer ~h_2~ ~(0 \le h_2 < h_1)~, but only if the rope is not covered in itching powder at height ~h_2~.

Both types of actions involved in this technique are understandably quite tiring, so Bob would like to avoid performing more of them than necessary. Help him determine the minimum number of actions he must perform to reach a height of at least ~H~ metres, or determine that it's sadly impossible for him to ever reach such a height.

Subtasks

In test cases worth 8/27 of the points, ~H \le 1\,000~ and ~J \le 2~.
In test cases worth another 12/27 of the points, ~H \le 1\,000~.

Input Specification

The first line of input consists of three space-separated integers, ~H~, ~J~, and ~N~.
~N~ lines follow, the ~i~-th of which consists of two space-separated integers, ~A_i~ and ~B_i~, for ~i = 1 \dots N~.

Output Specification

Output a single integer, either the minimum number of actions required for Bob to reach a height of at least ~H~ metres, or -1 if it's impossible for him to do so.

Sample Input 1

12 5 2
2 4
10 10

Sample Output 1

5

Sample Input 2

5 2 2
1 1
4 4

Sample Output 2

-1

Sample Explanation

In the first case, Bob can jump up to a height of ~5~, drop down to a height of ~1~, jump up to a height of ~6~, jump up to a height of ~11~, and finally jump up to a height of ~16~. This is the only strategy which involves ~5~ actions, which is the minimum possible number of actions.

In the second case, Bob must start by jumping up to a height of ~2~. From there, he may not jump upwards to a height of ~4~ (as the rope is covered in itching powder there), and similarly may not drop down to a height of ~1~, meaning that he can never grab the rope at any height aside from ~0~ or ~2~.