该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

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

• 跳过这一轮。
• $a_i$ 的代价获得 $1$ 颗星星。
• $b_i$ 的代价获得 $2$ 颗星星。
• $c_i$ 的代价获得 $3$ 颗星星。
• $d_i$ 的代价获得 $4$ 颗星星。

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

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

Input

本题有多组数据，第一行输入数据组数 $T$。

对于每组数据的第一行，有两个正整数表示 $n,k$。

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

$1 \leq n \leq 1000, 0 \leq k \leq n \times 4$。

满足 $\sum n \leq 100000$。

Output

对于每组数据，输出一个数字表示这组数据的答案。

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。