HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


World of Warlcraft

Section problems

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

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

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