Поликарп готовит первый контест по программированию для роботов. В этом контесте \(n\) задач, и большое количество самых разных роботов попробует их решить. Каждый робот, решивший задачу \(i\), получает \(p_i\) баллов, и итоговый результат робота в соревновании считается как сумма \(p_i\) по всем задачам \(i\), которые он решил. Для каждой задачи \(p_i\) — целое число не меньше \(1\).
Две компании, специализирующиеся на робототехнике, «Robo-Coder Inc.» и «BionicSolver Industries», также собираются отправить по одному роботу на соревнование. Поликарп знает все сильные и слабые стороны роботов, производимых этими компаниями, поэтому для каждой задачи он может точно предсказать, какие из этих двух роботов решат ее, а какие — не решат. Зная эту информацию, он может оценить результаты соревнования или повлиять на них.
По какой-то причине (которая совершенно точно никак не связана с подкупом) Поликарп хочет, чтобы робот «Robo-Coder Inc.» выступил лучше, чем робот «BionicSolver Industries». Поликарп хочет выставить баллы за задачи \(p_i\) таким образом, что робот «Robo-Coder Inc.» получит строго больше баллов, чем робот «BionicSolver Industries». Однако если значения \(p_i\) будут большими, то наблюдатели могут что-то заподозрить, поэтому Поликарп хочет минимизировать максимум \(p_i\) по всем задачам. Можете ли вы помочь Поликарпу определить минимально возможное верхнее ограничение на количество баллов за каждую задачу?
Выходные данные
Если роботу «Robo-Coder Inc.» ни при какой разбалловке не удастся набрать больше баллов, чем наберет робот «BionicSolver Industries», выведите одно число \(-1\).
Иначе выведите минимально возможное значение \(\max \limits_{i = 1}^{n} p_i\), при котором можно расставить такие значения \(p_i\), что робот «Robo-Coder Inc.» наберет строго больше баллов, чем робот «BionicSolver Industries».
Примечание
В первом примере одна из возможных разбалловок — следующая: \(p = [3, 1, 3, 1, 1]\). Тогда «Robo-Coder» получит \(7\) баллов, «BionicSolver» — \(6\) баллов.
Во втором примере оба робота получат \(0\) баллов, поэтому разбалловка ни на что не влияет.
В третьем примере оба робота решают все задачи, поэтому разбалловка также ни на что не влияет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 1 0 0
0 1 1 1 1
|
3
|
|
2
|
3
0 0 0
0 0 0
|
-1
|
|
3
|
4
1 1 1 1
1 1 1 1
|
-1
|
|
4
|
9
1 0 0 0 0 0 0 0 1
0 1 1 0 1 1 1 1 0
|
4
|