B. Потерянные чемоданы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, в авиакомпании «Беда» часто теряется багаж, и обеспокоенные журналисты решили рассчитать, какое наибольшее количество багажа может не вернуться к путешественникам.

Компания «Беда» осуществляет перелеты между $$$n$$$ аэропортами, которые пронумерованы от $$$1$$$ до $$$n$$$. Эксперимент журналистов продлится $$$m$$$ дней. Известно, что в полночь перед первым днем эксперимента в $$$j$$$-м аэропорту находилось $$$s_j$$$ потерянных чемоданов. В $$$i$$$-й день происходит следующее:

  • Утром одновременно вылетают $$$2n$$$ рейсов, среди них $$$n$$$ рейсов первого типа и $$$n$$$ рейсов второго типа.
    • $$$j$$$-й рейс первого типа летит из аэропорта $$$j$$$ в аэропорт $$$(((j-2) \bmod n )+ 1)$$$ (предыдущий аэропорт, для первого аэропорта — последний), в нем может быть перевезено не более $$$a_{i,j}$$$ потерянных чемоданов.
    • $$$j$$$-й рейс второго типа летит из аэропорта $$$j$$$ в аэропорт $$$((j \bmod n) + 1)$$$ (следующий аэропорт, для последнего аэропорта — первый), в нем может быть перевезено не более $$$c_{i,j}$$$ потерянных чемоданов.
  • Днём в аэропортах производится проверка потерянных чемоданов. Если после вылета рейсов в этот день в $$$j$$$-м аэропорту остаётся $$$x$$$ чемоданов и $$$x \ge b_{i, j}$$$, то хотя бы $$$x - b_{i, j}$$$ чемоданов находят, и они перестают быть потерянными.
  • Вечером все $$$2n$$$ рейсов завершаются, и перевозимые в этот день потерянные чемоданы оказываются в соответствующих аэропортах.

Для каждого $$$k$$$ от $$$1$$$ до $$$m$$$ журналисты хотят знать, какое наибольшее количество потерянных чемоданов может быть не найдено в ходе проверок в течение первых $$$k$$$ дней. Обратите внимание, что для каждого $$$k$$$ эти значения ищутся независимо.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 12$$$, $$$1 \le m \le 2000$$$) — количество аэропортов и количество дней эксперимента.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \le s_i \le 10^8$$$) — изначальное количество потерянных чемоданов в каждом аэропорту.

Далее по очереди следуют описания для каждого из $$$m$$$ дней.

Первая строка описания $$$i$$$-го дня содержит $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$0 \le a_{i, j} \le 10^8$$$) — максимальное количество потерянных чемоданов, которые могут перевозиться в предыдущий аэропорт, для каждого аэропорта.

Вторая строка описания $$$i$$$-го дня содержит $$$n$$$ целых чисел $$$b_{i,1}, \ldots, b_{i,n}$$$ ($$$0 \le b_{i, j} \le 10^8$$$) — минимальное количество потерянных чемоданов, которые будут найдены в $$$i$$$-й день в каждом аэропорту.

Третья строка описания $$$i$$$-го дня содержит $$$n$$$ целых чисел $$$c_{i,1}, \ldots, c_{i,n}$$$ ($$$0 \le c_{i, j} \le 10^8$$$) — максимальное количество потерянных чемоданов, которые могут перевозиться в следующий аэропорт, для каждого аэропорта.

Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2000$$$.

Выходные данные

Для каждого набора входных данных выведите $$$m$$$ целых чисел — максимальное количество не найденных чемоданов для каждого количества дней от $$$1$$$ до $$$m$$$.

Пример
Входные данные
2
5 3
1 1 1 1 1
0 0 1 0 0
0 1 0 0 1
1 0 0 1 0
0 1 0 0 0
9 0 9 9 9
0 1 0 0 0
0 0 0 0 0
9 0 9 0 0
0 0 0 0 0
3 1
0 100000000 5
0 100000000 5
0 100000000 5
0 100000000 5
Выходные данные
5
4
2
100000005
Примечание

В первом наборе входных данных:

  • В первый день могут не найти все $$$5$$$ чемоданов, так как потерянные чемоданы могут быть отправлены на рейсах из каждого аэропорта.
  • В утро второго дня во $$$2$$$-м аэропорту может быть не более чем $$$3$$$ чемодана, в $$$5$$$-м аэропорту может быть не более чем $$$2$$$ чемодана, а в остальных аэропортах чемоданов быть не может. Все чемоданы из $$$5$$$-го аэропорта могут остаться в нем же. А во $$$2$$$-м аэропорту не более чем $$$2$$$ чемодана могут быть отправлены в рейсах в соседние аэропорты. Таким образом, как минимум $$$1$$$ чемодан будет найден.
  • Под конец третьего дня потерянные чемоданы могут оказаться только в $$$1$$$-м и $$$2$$$-м аэропорту. Там их может быть не более чем по одному, а значит, суммарно останутся не найденными не более чем $$$2$$$ чемодана.
Найденные чемоданы отмечены зеленым цветом.

Во втором наборе входных данных все чемоданы могут остаться в своих аэропортах и проверка не найдет ни одного потерянного чемодана. Поэтому ответ равен $$$10^9 + 5$$$.