Впереди у студента Васи сессия, которая будет длиться n дней. Васе предстоит сдать экзамены по m предметам. Предметы пронумерованы от 1 до m.
Про каждый день известно, какой из m предметов можно сдать в этот день. Возможно, что в какой-то день нельзя сдавать ни один предмет. Однако в каждый день можно сдавать не более одного предмета.
В очередной день Вася может либо сдавать экзамен по тому предмету, который можно сдавать в этот день (сдача занимает весь день), либо готовиться весь день к экзамену по некоторому предмету, либо отдыхать.
Про каждый из предметов Вася знает число ai — количество дней, которые нужно готовиться, чтобы сдать экзамен по предмету номер i. Вася может переключаться между подготовкой к экзаменам, то есть необязательно готовиться непрерывно ai-е дней к экзамену номер i. Перемешивать порядок подготовки к экзаменам можно произвольным образом.
Перед вами стоит задача определить минимальный номер дня, в который Вася сможет закрыть сессию — то есть сдать экзамены по всем предметам, либо определить, что это невозможно сделать. Экзамен по каждому предмету нужно сдать ровно один раз.
Выходные данные
Выведите целое число — минимальный номер дня, в который Вася сможет сдать все экзамены. Если это невозможно, выведите -1.
Примечание
В первом тестовом примере Вася может дейстовать следующим образом. В первый и второй день готовиться к экзамену номер 1 и сдать его в пятый день, а между этим подготовиться к экзамену номер 2 в третий день и сдать его в четвёртый.
Во втором тестовом примере Вася должен готовиться к экзамену номер 3 первые четыре дня и сдать его в пятый день. Затем в шестой день подготовиться к экзамену номер 2 и сдать его в седьмой день. После этого ему нужно подготовиться к экзамену номер 1 за восьмой день и сдать его в девятый день.
В третьей тестовом примере Вася не сможет сдать единственный экзамен, так как не успеет к нему подготовиться.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
0 1 0 2 1 0 2
2 1
|
5
|
|
2
|
10 3
0 0 1 2 3 0 2 0 1 2
1 1 4
|
9
|
|
3
|
5 1
1 1 1 1 1
5
|
-1
|