题目描述

小 A 有 $n$ 次获得星星的机会。

在第 $i$ 次机会里他有如下的 $5$ 种选择（他必须做出恰好一种选择）：

1、跳过这一轮。

2、$a_i$ 的代价获得 $1$ 颗星星。

3、$b_i$ 的代价获得 $2$ 颗星星。

4、$c_i$ 的代价获得 $3$ 颗星星。

5、$d_i$ 的代价获得 $4$ 颗星星。

保证 $0\le a_i\le b_i\le c_i\le d_i \le 10^9$。

他想要获得恰好 $k$ 颗星星，但是并不知道最小代价是多少，请你帮他计算这个最小值。

输入格式

第一行 $1$ 个整数 $T$ ($1\le T \le 100$)，代表测试样例个数。

对于每组数据的第一行，有两个正整数表示 $n$（$1\le n \le 1000$），$k$（$0\le k \le n \times 4$）。

接下来 $n$ 行，输入四个数字 $a_i,b_i,c_i,d_i$。

满足 $\sum n \le 100000$。

输出格式

输出 $T$ 行，每行一个数表示答案。

输入样例

1
5 10
8 9 10 15
4 6 7 15
4 7 12 15
6 8 10 14
1 8 10 13

输出样例

28

提示

依次选择 $3,3,0,3,1$，代价是 $10,7,0,10,1$。