statement.md

Description

ハイラノレ王国に昔から伝わる儀式として、Professionals Pass All Problems(PPAP)という儀式がある。この儀式を1回行うためには、ペン2本、リンゴ1個、パイナップル1個を必要とする。この儀式によってハイラノレ王国はずっと平和を保ってきた。

儀式は1人の巫女によって行う。巫女の家系の跡取りとして生まれたゼノレダは、この儀式を行うために日々修行している。この儀式を修得するために、あとは本番と同じ練習を $x$ 回することを残すのみとなった。つまり、ゼノレダはPPAPを修得するためにペンを $2x$ 本以上、リンゴを $x$ 個以上、パイナップルを $x$ 個以上買おうと思っている。

王国には $N$ 軒のテソーの店があり、そこではペン $a_i$ 個、リンゴ $b_i$ 個、パイナップル $c_i$ 個を1セットにして $r_i$ ルビーで売っている。1軒のテソーの店から、何セットでも買うことが可能である。 ゼノレダがPPAPを修得するために、必要な金額の最小値を求めよ。 買い揃えることが不可能なら-1と答えよ。

Constraints

• $1 \le N \le 50$
• $1 \le x \le 50$
• $0 \le a_i, b_i, c_i \le 50$ (ただし、$a_i + b_i + c_i \ge 1$)
• $1 \le r_i \le 10^5$

Input

1つの入力ファイルは複数のテストケースからなる。

入力ファイルの最初の1行目にはテストケースの個数 $T$ が記される $(1 \le T \le 50)$ 。

2行目以降には、T個のテストケースが記述されており、各テストケースは次の形式で表される。

$N$ $x$
$a_1$ $b_1$ $c_1$ $r_1$
$a_2$ $b_2$ $c_2$ $r_2$
$\vdots$
$a_N$ $b_N$ $c_N$ $r_N$

Output

各テストケースごとに、必要な金額の最小値を、または実現不可能な場合は-1を、1行ずつ出力せよ。

Sample Input

4
3 4
3 0 0 6
0 1 0 2
0 0 5 18
1 50
1 1 1 100
2 4
1 2 1 10
2 1 1 20
2 10
3 1 2 80
1 2 1 70

Sample Output

44
10000
80
620

1つ目のケースでは、3軒のテソーの店が別々にペンとリンゴとパイナップルを売っているので、それぞれで必要な分を買うのが最適である。

2つ目のケースでは、王国にテソーの店は1つしかない。50回PPAPをするためにはペンが100本必要なので、このセットを100セット買う。

3つ目のケースでは、2軒目から4セットを買うのが最適である。

4つ目のケースでは、1軒目から6セット、2軒目から2セットを買うのが最適である。