Виктор хочет стать «Мистером совершенство». Для этого ему нужно овладеть определенным набором навыков. Более точно, у него есть \(2\) навыка, которые ему нужно овладеть.
У него также есть \(n\) книг. Чтение книги \(i\) занимает у него \(m_i\) минут и дает ему некоторые (возможно, ни одного) из двух необходимых навыков, представленных двоичной строкой длины \(2\).
Какое минимальное количество времени потребуется, чтобы Виктор овладел обоими необходимыми навыками?
Выходные данные
Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество минут, необходимое для того, чтобы Виктор овладел обоими необходимыми навыками, и \(-1\), если невозможно овладеть двумя навыками после чтения любого количества книг.
Примечание
В первом тестовом случае мы можем использовать книги \(2\) и \(3\), с общим количеством потраченного времени, равным \(3 + 4 = 7\).
Во втором тестовом случае мы можем использовать книги \(1\) и \(4\), с общим количеством потраченного времени, равным \(3 + 2 = 5\).
В третьем тестовом случае у нас есть только один вариант, и это чтение книги \(1\) за общее количество потраченного времени, равное \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
2 00
3 10
4 01
4 00
5
3 01
3 01
5 01
2 10
9 10
1
5 11
3
9 11
8 01
7 10
6
4 01
6 01
7 01
8 00
9 01
1 00
4
8 00
9 10
9 11
8 11
|
7
5
5
9
-1
8
|