题意

拿到了 NOI Ag 后，你不得不回来学习文化课。

由于你从来没有上过课，现在你六科的成绩全部为零。

你希望高考时，每一科都能至少考到 $k$ 分。

你有 $n$ 种学习计划。执行这种计划需要 $C_i$ 天。执行完后，你的第 $j$ 科成绩会增加 $A_{ij}$。每种学习计划只能用一次。

现在你希望知道，运用这些学习计划，你在保证每科至少 $k$ 分的前提下，至少需要多少天。

你无需让分数最大。

输入格式

第一行两个正整数 $n, k$，表示学习计划的数量与你每一科都至少达到的分数。

接下来 $n$ 行，第 $i$ 行 $7$ 个正整数，表示 $A_{i1}, A_{i2}, A_{i3}, A_{i4}, A_{i5}, A_{i6}, C_i$。

输出格式

一行一个正整数，表示至少需要的天数。

如果不可能完成，输出 $-1$。

样例

输入 #1

7 3
3 2 1 2 1 1 50
3 3 1 1 2 1 28
3 1 2 2 2 3 31
1 3 2 3 2 1 3
1 2 2 3 3 2 39
2 3 3 3 1 2 40
2 3 2 1 3 3 30

输出 #1

33

输入 #2

14 3
1 2 1 2 3 2 207777879
1 2 3 1 3 1 663545441
2 2 2 3 1 3 666099002
2 3 3 2 3 2 537240814
1 2 2 1 1 3 31062042
2 3 2 3 2 1 401746516
1 2 2 3 2 3 658425776
2 3 1 1 1 1 802876061
2 1 1 1 2 2 626689750
2 3 2 1 2 3 832226959
2 1 1 2 1 2 137349025
1 2 3 2 1 1 614224125
3 2 1 3 3 3 858554411
2 2 3 2 1 3 889960917

输出 #2

376188946

数据范围

\begin{array}{|c|c|c|} \hline \textbf{Subtask} & \max n & \max k & A_{ij} & C_i & \textbf{Score} \\ \hline 1 & 10 & 6 & 1 \le A_{ij} \le k & 1 \le C_i \le 10^3 & 20 \\ \hline 2 & 20 & 6 & 1 \le A_{ij} \le k & 1 \le C_i \le 10^9 & 30 \\ \hline 3 & 100 & 6 & 1 \le A_{ij} \le k & 1 \le C_i \le 10^9 & 50 \\ \hline \end{array}

本题 Subtask 内捆绑测试。