YOU: "So you were the head chef for this event. Is that the role you wanted?"

PATRICK: "It's not the role I expected, but honestly, I had a great time learning how to cook!"

YOU: "What were you expecting instead?"

PATRICK: "I don't know, figured I'd just be helping out. Kevin sort of threw it at me last minute. Wasn't planning on running the whole kitchen, but it was fine. He had a way of just deciding things for you like that."

YOU: "Did you hear anything unusual that night? Anything from backstage?"

PATRICK: "Nah, it's loud in here. Pots, extractor fans, the works. Zach came by at some point, we talked algorithms for a bit. That's about it. Man, it just sucks to hear about Kevin though. Known him for years. Good guy. Should've gone and said hi to him at some point that night. Didn't get the chance.

Make sure you catch whoever did this."

It's Patrick's responsibility to cook all the food for the ACPC Ball. Unfortunately, Patrick has never cooked a single thing in his life, so he'll need to study hard in order to learn everything in time.

Patrick's cookbook has ~n~ pages, which he plans to read in order from the first page to the last. He also has ~m~ focus values ~f_1, f_2, \ldots, f_m~ satisfying ~n \geq f_1 > f_2 > \cdots > f_m > 0~. On his ~i~th consecutive day of reading, Patrick can read at most ~f_i~ pages.

Patrick may rest on any day instead of reading. A single day of rest clears his exhaustion: the next time he reads, it again counts as his first consecutive reading day, allowing up to ~f_1~ pages. Because his focus values only extend to ~f_m~, Patrick cannot read more than ~m~ days in a row. After ~m~ consecutive reading days, he is too exhausted and must rest before reading again.

To keep himself on track, Patrick has set ~k~ checkpoints for himself. The ~i~th checkpoint ~(d_i, x_i)~ requires that by the end of day ~d_i~, Patrick has read at least ~x_i~ pages in total. If Patrick ever fails a checkpoint, he gives up and asks ChatGPT for the recipes instead, which would be catastrophic for the guests.

Determine the minimum number of days required for Patrick to finish the entire cookbook without failing any checkpoint, or output ~-1~ if this is impossible.

Input

The first line contains three integers ~n~, ~m~, and ~k~ ~(1 \leq n \leq 2 \times 10^3, 1 \leq m \leq 100, 0 \leq k \leq 2n - 1)~, the number of pages in Patrick's cookbook, the number of focus values, and the number of checkpoints.

The second line contains ~m~ integers ~f_1, f_2, \cdots, f_m~ (~n \geq f_1 > f_2 > \cdots > f_m > 0~), indicating that Patrick can read up to ~f_i~ pages on his ~i~th consecutive reading day.

The next ~k~ lines each contain two integers ~d_i~ and ~x_i~ ~(1 \leq d_i \leq 2n - 1, 1 \leq x_i \leq n)~, indicating that by the end of day ~d_i~, Patrick must have read at least ~x_i~ pages. Checkpoints are given in strictly increasing order of ~d_i~.

Output

Output a single integer, the minimum number of days required for Patrick to finish his cookbook without failing any checkpoint, or output ~-1~ if this is impossible.

Example

Input 1

19 3 2
10 5 3
2 12
3 15

Output 1

4

Patrick can read all ~19~ pages in ~4~ days as follows:

Note that Patrick only needs ~4~ pages on day ~4~ but he could have read up to ~f_1 = 10~.

Input 2

19 3 0
10 5 3

Output 2

3

Patrick can read ~10~ pages, then rest, then read another ~10~ pages. This was not possible in the previous case due to Patrick's checkpoints.

Input 3

15 5 5
5 4 3 2 1
1 5
2 9
3 12
4 14
5 15

Output 3

5

To meet his checkpoints, Patrick must read for 5 days in a row without resting.

Input 4

15 5 2
5 4 3 2 1
1 5
2 10

Output 4

-1

The second checkpoint requires ~10~ pages by day ~2~, but Patrick can read at most ~9~ pages in his first two days, so it is impossible for him to pass this checkpoint.