Аркадий — заядлый игрок в Gardenscapes. Аркадий хочет построить два новых фонтана. Есть список из n доступных ему фонтанов, про каждый фонтан известна его красота и стоимость. В игре есть два вида денежных ресурсов: монеты и алмазы, поэтому стоимость каждого из фонтанов может быть выражена в монетах или алмазах. Монеты и алмазы нельзя обменивать друг на друга.
Помогите Аркадию выбрать два фонтана с максимальной суммарной красотой таких, что он может купить на имеющиеся у него ресурсы оба одновременно.
Выходные данные
Выведите максимальную суммарную красоту ровно двух фонтанов, которые Аркадий может построить. Если невозможно построить два фонтана, выведите 0.
Примечание
В первом примере Аркадию нужно построить второй фонтан с красотой 4, который стоит 3 монеты. Первый фонтан он построить не сможет, так как ему не хватит на это монет. Также, Аркадию нужно построить третий фонтан с красотой 5, который стоит 6 алмазов. Таким образом, суммарная красота построенных фонтанов равна 9.
Во втором примере всего два фонтана, но Аркадий не сможет построить их оба, так как для постройки первого фонтана нужно 5 монет, а у Аркадия есть всего 4 монеты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 7 6
10 8 C
4 3 C
5 6 D
|
9
|
|
2
|
2 4 5
2 5 C
2 1 D
|
0
|
|
3
|
3 10 10
5 5 C
5 5 C
10 11 D
|
10
|