1748. Хомяки

В поисках пропитания большая дружная семья кроликов добрела до морковного поля. К сожалению, чуть раньше сюда же прибыла большая дружная семья голодных хомяков. Во избежание конфликта было решено собирать урожай по очереди. Поле представляет собой `N` грядок по `M` кустов; на каждом кусте растет некоторое количество морковок. Очередной собирающий стартует от любого куста первой грядки и движется к последней, переходя от одного куста к другому по следующему правилу: от куста номер `K` на грядке `L` можно перейти только на грядку `L+1` к одному из трех кустов с номерами `K-1`, `K`, `K+1` (конечно, если кусты с такими номерами есть). Каждый посещенный куст очищается от моркови полностью. Первым на сбор урожая выходит один из кроликов, следом идет хомяк, потом снова кролик и так до тех пор, пока на поле есть хоть одна морковка.

Кролики суетливы, поэтому они выбирают путь наиболее выгодный внешне: стартуют от самого богатого куста первой грядки, а из трех последующих вариантов всегда выбирают самый большой куст (при наличии нескольких кустов с одинаковым числом морковок выбирается куст с наибольшим номером). Хомяки, прибыв на поле раньше, успели составить подробную карту поля и поддерживают её в актуальном состоянии на основе оперативных данных о сборе урожая, поэтому они для каждого хомяка выбирают путь, позволяющий собрать максимальное количество морковок из возможных (при наличии нескольких вариантов с максимально возможным количеством морковок выбирается путь через куст с наибольшим номером).

По известной карте поля определите, сколько моркови удалось собрать кроликам и хомякам по отдельности.

Первая строка входного файла содержит число тестов. Каждый тест начинается с двух целых чисел `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 100`). Следом идут `N` строк, в каждой из которых `M` чисел `X_{i,j}` (`0\ ≤\ X_{i,j}\ ≤\ 10`). `X_{i,j}` – количество морковок на `j`-ом кусте `i`-ой грядки.

Для каждого теста на отдельной строке выведите через пробел два числа: количество морковок, собранных кроликами и хомяками, соответственно.

2
3 3
1 1 2
1 1 1
10 1 1
4 4
1 1 1 2
1 1 1 1
1 1 1 1
10 10 1 1

7 12
18 17