В некотором клубе планируется вечеринка, и на нее будут приглашены некоторые из \(n\) участников этого клуба. Все \(n\) участников пронумерованы числами \(1, 2, \dots, n\). Если \(i\)-й участник не будет приглашен, уровень уныния на вечеринке увеличится на \(a_i\).
Среди \(n\) участников клуба \(m\) пар друзей. Если оба человека из пары друзей будут приглашены на вечеринку, по традиции они должны будут съесть тортик на двоих. Таким образом, на вечеринке будет съедено ровно столько тортиков, сколько будет пар друзей, в которых оба участника приглашены.
Для вечеринки клуб закажет несколько пар тортиков. Поэтому необходимо, чтобы на вечеринке было съедено четное число тортиков.
Чему равен минимальный возможный уровень уныния на вечеринке, если пригласить участников так, что будет съедено четное число тортиков?
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное возможное значение уныния.
Примечание
В первом наборе входных данных можно пригласить всех участников. Уровень уныния будет равен \(0\).
Во втором наборе возможны следующие варианты:
- пригласить участников \(1\) и \(2\) — \(0\) тортиков, уныние \(3\);
- пригласить участников \(2\) и \(3\) — \(0\) тортиков, уныние \(2\);
- пригласить только участника \(1\) — \(0\) тортиков, уныние \(4\);
- пригласить только участника \(2\) — \(0\) тортиков, уныние \(5\);
- пригласить только участника \(3\) — \(0\) тортиков, уныние \(3\);
- не пригласить никого — \(0\) тортиков, уныние \(6\).
Минимальное значение уныния достигается при приглашении участников \(2\) и \(3\).
В третьем примере приглашение участников \(3,4,5\) дает подходящую вечеринку с минимальным возможным значением уныния.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1
|
0
2
3
2
|