Хом`яки та кролики
У пошуках їжі велика дружна сім'я кроликів добрела до морков'яного поля. На жаль, чуть раніше сюди ж прибула велика дружна сім'я голодних хом'яків. Для уникнення конфлікту було вирішено збирати врожай по черзі. Поле яввляє собою 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-ої грядки.
Вихідні дані
Для кожного тесту в окремому рядку вивести два числа: кількість морквин, зібраних кроликами та хом'яками, відповідно.