Лиса Сиель играет в карты со своим другом, лисом Джиро. На столе лежат n стопок карт и на каждой карте записано по положительному целому числу.
Игроки ходят по очереди, Сиель начинает. В свой ход она берет одну карту сверху любой непустой стопки. Джиро на своем ходу берет одну карту снизу любой непустой стопки. Каждый игрок хочет максимизировать общую сумму чисел на взятых им картах. Игра заканчивается, когда все стопки пустые.
С каким счетом закончится игра при условии, что Сиель и Джиро играют оптимально?
Выходные данные
Выведите два целых числа: сумму карт Сиель и сумму карт Джиро, если они играют оптимально.
Примечание
В первом примере Сиель возьмет карты с числами 100 и 1, Джиро возьмет карту с числом 10.
Во втором примере Сиель возьмет карты с числами 2, 8, 6, 5, 9, а Джиро возьмет карты с числами 4, 7, 1, 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 100
2 1 10
|
101 10
|
|
2
|
1
9 2 8 6 5 9 4 7 1 3
|
30 15
|
|
3
|
3
3 1 3 2
3 5 4 6
2 8 7
|
18 18
|
|
4
|
3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000
|
7000 7000
|