\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 Для кожного тесту в окремому рядку вивести найбільший прибуток, який можна отримати від поїздки.