Герой очень хочет славы, поэтому он сражается с монстрами.
У героя есть \(n\) способностей. \(i\)-я способность имеет тип \(a_i\) (любой из огонь или мороз) и исходный урон \(b_i\).
Герой может использовать все \(n\) способностей в любом порядке (каждая способность будет использована только один раз). При использовании каждой способности, происходит следующее:
- Если текущая способность следует сразу за способностью другого типа, то её урон удваивается.
Другими словами,
- Если способность типа огонь с исходным уроном \(c\) используется сразу после способности с типом огонь, тогда она нанесет \(c\) урона;
- Если способность типа огонь с исходным уроном \(c\) используется сразу после способности с типом мороз, тогда она нанесет \(2c\) урона;
- Если способность типа мороз с исходным уроном \(c\) используется сразу после способности с типом огонь, тогда она нанесет \(2c\) урона;
- Если способность типа мороз с исходным уроном \(c\) используется сразу после способности с типом мороз, тогда она нанесет \(c\) урона.
Ваша задача найти максимальный урон, который может нанести герой.
Выходные данные
Для каждого набора входных данных выведите максимальный урон, который может нанести герой.
Примечание
В первом наборе входных данных мы можем применить способности в порядке \([3, 1, 4, 2]\), и суммарный урон будет \(100 + 2 \times 1 + 2 \times 1000 + 10 = 2112\).
Во втором наборе входных данных мы можем применить способности в порядке \([1, 4, 2, 5, 3, 6]\), и суммарный урон будет \(3 + 2 \times 6 + 2 \times 4 + 2 \times 7 + 2 \times 5 + 2 \times 8 = 63\).
В третьем наборе входных данных мы можем применить способности в порядке \([1, 2, 3]\), и суммарный урон будет \(1000000000 + 1000000000 + 1000000000 = 3000000000\).
В четвертом примере всего одна способность с уроном \(1\), значит суммарный урон будет \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
0 1 1 1
1 10 100 1000
6
0 0 0 1 1 1
3 4 5 6 7 8
3
1 1 1
1000000000 1000000000 1000000000
1
1
1
|
2112
63
3000000000
1
|