ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


World of Warlcraft

Задачи раздела

• A+B
• Amuz Deluxe
• C++ и Java
• Captcha
• Hello World
• Radar Defence
• World of Warlcraft
• World of Warlcraft
• World of Warlcraft
• XOR на прямоугольнике
• XOR на прямоугольнике (усложнё...
• You're in the army now
• Автоформатирование
• Анаграмма
• Анаграмма
• Асимптотика
• Асимптотика

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

World of Warlcraft Обратите внимание на советы для начинающих.
World of Warlcraft
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У Максима есть персонаж первого уровня, которого нужно прокачать до уровня 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
Для отправки решений необходимо выполнить вход.

www.contester.ru