У Максима есть персонаж первого уровня, которого нужно прокачать до уровня N. Чтобы персонаж, имеющий уровень i, получил следующий уровень i + 1, нужно заработать Ai очков.
Максим знает M локаций, на которых удобно прокачивать персонажа. Чтобы прийти на j-ю локацию, нужно иметь уровень не менее Lj, а за зачистку этой локации персонаж получает Pj очков. За повторное прохождение уже зачищенной локации очков не присуждается.
Помогите Максиму узнать, сколько локаций нужно зачистить, чтобы персонаж получил уровень N.
Выходные данные
Выведите одно целое число — минимальное количество локаций, зачистка которых позволит получить уровень N.
Если персонаж Максима не сможет получить уровень N, выведите -1.