Хом'яки та кролики#430
У пошуках їжі велика щаслива родина кроликів прибула на морквяне поле. На жаль, буквально перед ними туди потрапила велика щаслива родина голодних хом'яків. Щоб уникнути конфлікту, вирішили збирати врожай по черзі. Поле складається з рядків, у кожному кущів; на кожному кущі росте деяка кількість морквин. Збирач врожаю стартує з будь-якого куща першого рядка й рухається до останнього рядка так: з куща номер у рядку можна перейти лише до куща з номером k-1, або k+1 у рядку l+1 (якщо кущ із таким номером існує). Кожен відвіданий кущ повністю очищається від морквин. Першими збирають врожай кролики, потім хом'яки, потім знову кролики і так далі, поки на полі лишається хоча б одна морквина.
Кролики поспішні, тому вибирають найочевидніший прибутковий шлях: стартують з найбагатшого на моркву куща першого рядка і на кожному кроці з трьох варіантів обирають кущ із найбільшою кількістю морквин (якщо кущів із максимальною кількістю декілька, обирають кущ із більшим номером). Хом'яки, прибувши раніше, встигли скласти детальну карту поля та оновлюють її після кожного збору, тому кожен хом'як обирає шлях, який дозволяє зібрати максимально можливу кількість морквин (якщо є декілька шляхів із однаковою максимальною сумою, обирають шлях через кущ із більшим номером).
За картою поля визначте, скільки морквин окремо зберуть кролики та хом'яки.
Перший рядок містить число тестів. Кожен тест починається з двох цілих чисел і (1 \leq n, m \leq 100). Далі йдуть рядків по цілих чисел x_{i,j} (0 \leq x_{i,j} \leq 10). x_{i,j} — кількість морквин на -му кущі -го рядка.
Для кожного тесту в окремому рядку виведіть два числа: кількість морквин, зібраних кроликами, і кількість морквин, зібраних хом'яками відповідно.
Приклад 1