열차 승차권 배분

한 열차가 1번 역에서 출발해 번호 순서대로 역을 지나 $N$번 역에서 멈춘다. $i < j$이면 $i$번 역에서 $j$번 역까지 가는 승차권을 팔 수 있다.

법으로 $i$번 역에서 $j$번 역까지 가는 승차권 가격 $C_{ij}$가 미리 정해져 있고, 그 구간의 수요 $D_{ij}$도 출발 전에 정확히 알 수 있다. 그래서 각 구간의 승차권을 0장부터 $D_{ij}$장까지 원하는 만큼 팔 수 있다. 정부는 여기에 더해 $i$번 역에서 $j$번 역까지 가는 무료 승차권 $O_{ij}$장을 따로 확보한다. 무료 승차권을 쓰는 승객도 자리를 차지하지만 수입은 없다.

열차 정원은 $P$명이다. 이웃한 두 역 사이의 어느 구간에서도 무료 승차권 승객을 포함한 탑승객 수가 $P$를 넘으면 안 된다. 정원을 넘겨 파는 것은 허용하지 않는다.

승차권을 가장 잘 배분했을 때 얻는 수입을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 역의 수 $N$과 열차 정원 $P$가 주어진다. 이어지는 $N-1$개 줄에는 승차권 가격이 주어진다. 그중 $i$번째 줄에는 $N-i$개의 수가 있고, 그 줄의 $j$번째 수가 $i$번 역에서 $i+j$번 역까지 가는 승차권 가격 $C_{i,i+j}$이다. 다음 $N-1$개 줄에는 같은 형식으로 수요 $D_{ij}$가 주어지고, 그다음 $N-1$개 줄에는 같은 형식으로 정부가 확보한 무료 승차권 수 $O_{ij}$가 주어진다.

• $0 < T \le 100$
• $3 \le N \le 16$
• $0 < P \le 200$
• $0 < C_{ij} \le 1000$
• $0 \le D_{ij} \le 250$
• $0 \le O_{ij} \le 20$
• 무료 승차권만으로 정원을 넘는 경우는 없다.

각 테스트 케이스마다 얻을 수 있는 최대 수입을 한 줄에 하나씩 출력한다.