Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Уважаемые участники, убедитесь, что вы прочитали руководство (и особенно раздел «Полезные советы и важные замечания»)!
У Максима есть персонаж первого уровня, которого нужно прокачать до уровня N. Чтобы персонаж, имеющий уровень i, получил следующий уровень i + 1, нужно заработать Ai очков.
Максим знает M локаций, на которых удобно прокачивать персонажа. Чтобы прийти на j-ю локацию, нужно иметь уровень не менее Lj, а за зачистку этой локации персонаж получает Pj очков. За повторное прохождение уже зачищенной локации очков не присуждается.
Помогите Максиму узнать, сколько локаций нужно зачистить, чтобы персонаж получил уровень N.
Входные данные
Первая строка содержит целое число N (2 <= N <= 1000) — желаемый уровень персонажа.
Вторая строка содержит N - 1 целое число Ai (1 <= Ai <= 1000) — количества очков, необходимые для перехода с i-го уровня на (i + 1)-й.
Третья строка содержит целое число M (1 <= M <= 1000) — количество локаций.
Следующие M строк содержат пары целых чисел Lj и Pj (1 <= Lj <= N, 1 <= Pj <= 5000) — соответственно минимальный уровень, позволяющий прийти на j-ю локацию, и количество очков за её зачистку.
Выходные данные
Выведите одно целое число — минимальное количество локаций, зачистка которых позволит получить уровень N.
Если персонаж Максима не сможет получить уровень N, выведите -1.
Примеры
| Входные данные | Выходные данные |
5
10 20 30 40
5
1 4
1 6
2 20
3 30
4 40 | 5 |
5
10 20 30 40
7
1 4
1 6
3 30
3 15
2 15
2 10
4 40 | 6 |
5
10 20 30 40
1
1 40 | -1 |
Для отправки решений необходимо выполнить вход.
|