\includegraphics{https://static.e-olymp.com/content/0a/0aa8d25f5c7f14865c585c21e7a4bb6c2ef144b6.jpg} Тор Гунар - большой поклонник поездов. Всю свою жизнь он бегал кругами по дому с криками "Ту-Ту". И когда появилась вакансия в местной железнодорожной компании, он немедленно туда устроился. Тор Гунар прилежно учился, и поэтому без труда получил эту работу. Это был самый счастливый момент в его жизни! К его великому разочарованию он обнаружил, что в контракте ничего не сказано о вождении поездов целый день. Сейчас Тора направили в департамент IT технологий, где он должен написать новую систему управления билетами. Часть, которую он должен написать, является алгоритмом распределения билетов среди пассажиров на различных маршрутах. Тор Гунар живет в странной стране. В добавок к тому что язык на котором он говорит является не совсем понятным, так еще и правительство его страны приняло некоторые странные законы согласно которым происходит продажа билетов. Например, цена путешествия от станции \textbf{A} до станции \textbf{B} является заранее установленной величиной. Каждый раз, продавая билет на поездку, Вы в точности знаете спрос на путешествия между каждой парой городов. Кроме того, правительство может резервировать некоторое количество билетов для себя (разумеется, бесплатно). Одна поездка на поезде проходит через несколько станций. Ехать со станции \textbf{A} до \textbf{B} можно лишь в том случае, если \textbf{A} предшествует \textbf{B} в списке станций. Известна вместимость каждого поезда, и между двумя соседними станциями нельзя перевезти больше пассажиров чем это значение. Тор Гунар задумался и нуждается в Вашей помощи. Напишите программу, которая наилучшим образом поможет распределить билеты. \InputFile Первая строка содержит количество тестов \textbf{T }(\textbf{0} < \textbf{T} ≤ \textbf{100}). Каждый тест начинается строкой, содержащей два числа \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{16}) и \textbf{P} (\textbf{0} < \textbf{P} ≤ \textbf{200}), соответственно количество станций и вместимость поезда. Далее следует \textbf{N }- \textbf{1} строка, описывающие стоимости билетов \textbf{C_ij} (\textbf{0} < \textbf{C_ij} ≤ \textbf{1000}). \textbf{i}-ая из этих \textbf{N} строк содержит \textbf{N }- \textbf{i} чисел. \textbf{j}-ое число \textbf{i}-ой строки является стоимостью билета со станции \textbf{i} до станции\textbf{ i }+ \textbf{j}. Следующие \textbf{N }- \textbf{1} строк описывают спрос на билеты для каждой станции \textbf{D_ij} (\textbf{0} ≤ \textbf{D_ij} ≤ \textbf{250}) в том же формате как и цены. Следующие \textbf{N }- \textbf{1} строк в том же формате описывают множество билетов, зарезервированное правительством \textbf{O_ij} (\textbf{0} ≤ \textbf{O_ij} ≤ \textbf{20}). Поездка на поезде начинается на станции \textbf{1} и заканчивается на станции \textbf{N}. Помните, что количество пассажиров плюс число зарезервированных мест для правительственных нужд не может превосходить вместимость поезда. Перегружать поезд запрещено. Правительство никогда своими требованиями (бесплатными билетами) не будет перегружать поезд. \OutputFile Для каждого теста в отдельной строке вывести наибольшую прибыль, которую можно получить от поездки.