Tor Gunnar 是一个火车迷。他一生都在家里跑来跑去大喊“嘟嘟”。因此，当他最近发现当地一家火车公司有职位空缺时，他立即申请了。Tor Gunnar 在为了获得这些机会而努力学习后，得到了这份工作。这是他一生中最快乐的时刻！然而，令他非常失望的是，他发现合同里根本没提可以整天坐火车。他现在被分配到 IT 部门，负责协助编写一个新的票务管理系统。他需要编写的部分是一个用于在火车路线上的不同可能行程之间分配车票的算法。

Tor Gunnar 来自一个奇怪的国家。除了说一种连他自己都不懂的语言外，该国政府还通过了一些影响火车票销售的奇怪法律。这意味着从车站 A 到车站 B 的旅行价格是预先确定的。此外，每次你为特定的行程售票时，你都会确切地知道每对城市之间的旅行需求。更重要的是，政府被允许为他们自己的用途预留一些车票（这些车票是免费的）。

一次火车行程由一系列车站组成。只要 A 在车站列表中位于 B 之前，就可以从车站 A 旅行到车站 B。每列火车都有给定的载客量，在任意两个相邻车站之间，乘客人数绝不能超过这个载客量。

Tor Gunnar 完全被难住了，迫切需要你的帮助。请编写一个程序，帮助他找出最佳的车票分配方案。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含两个数字 $N$ 和 $P$，分别表示车站数量和火车的载客量。接下来是 $N - 1$ 行，给出票价 $C_{ij}$。这 $N$ 行中的第 $i$ 行包含 $N - i$ 个数字。第 $i$ 行的第 $j$ 个数字是从车站 $i$ 到车站 $i + j$ 的票价。接下来的 $N - 1$ 行以相同的格式给出每对车站的车票需求 $D_{ij}$。再接下来的 $N - 1$ 行以相同的格式给出政府官员预留的车票数量 $O_{ij}$。

输出格式

对于每个测试用例，输出一个单独的数字。该数字应等于火车行程可能获得的最大收入。

数据范围

• $0 < T \leq 100$
• $3 \leq N \leq 16$
• $0 < P \leq 200$
• $0 < C_{ij} \leq 1000$
• $0 \leq D_{ij} \leq 250$
• $0 \leq O_{ij} \leq 20$
• 火车行程从车站 1 到车站 $N$。
• 请记住，包括政府官员在内的乘客总数不能超过载客量。
• 不允许火车超载。
• 政府绝不会使用他们的“免费”车票使你的火车超载。

样例

输入 1

1
3 4
6 7
3
4 1
1
2 1
0

输出 1

10