Монокарп — самый известный вор в Берляндии. В этот раз он решил украсть два бриллианта. К несчастью для Монокарпа, за бриллиантами следят \(n\) камер. У каждой из камер есть два параметра \(t_i\) и \(s_i\). Первый параметр определяет, следит ли камера только за первым бриллиантом (\(t_i=1\)), только за вторым (\(t_i=2\)), или за обоими (\(t_i=3\)). Второй параметр определяет количество секунд, которое камера будет отключена после ее взлома.
Монокарп каждую секунду может выполнять одно из трех действий:
- ничего не делать;
- выбрать любую камеру и взломать ее; если взломать \(i\)-ю камеру, она будет отключена в следующие \(s_i\) секунд (если номер текущей секунды — \(T\), то камера будет отключена в секунды с \((T+1)\) по \((T+s_i)\), включительно);
- украсть бриллиант, если все камеры, которые следили за ним, отключены в эту секунду. Второй бриллиант можно красть только после того, как украден первый.
Обратите внимание, что Монокарп может взламывать камеру повторно, даже если она отключена.
Ваша задача — определить минимальное время, за которое Монокарп украдет сначала первый бриллиант, а затем второй, или сообщить, что это невозможно.
Выходные данные
Выведите одно целое число — минимальное время, за которое Монокарп украдет сначала первый бриллиант, а затем второй. Если это невозможно, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 6
1 2
1 2
2 1
|
6
|
|
2
|
4
2 8
3 2
3 2
3 5
|
9
|
|
3
|
2
3 2
2 3
|
4
|
|
4
|
1
3 1
|
4
|
|
5
|
8
2 1
2 2
3 5
3 6
1 2
1 3
1 4
1 5
|
11
|