星星
Time Limit : 4000/200ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小 A 有 $n$ 次获得星星的机会。
在第 $i$ 次机会里他有如下的 $5$ 种选择（他必须做出恰好一种选择）：
- 跳过这一轮。
- $a_i$ 的代价获得 $1$ 颗星星。
- $b_i$ 的代价获得 $2$ 颗星星。
- $c_i$ 的代价获得 $3$ 颗星星。
- $d_i$ 的代价获得 $4$ 颗星星。
保证 $0 < a_i \leq b_i \leq c_i \leq d_i \leq 10^9$。
他想要获得恰好 $k$ 颗星星，但是并不知道最小代价是多少，请你帮他计算这个最小值。
在第 $i$ 次机会里他有如下的 $5$ 种选择（他必须做出恰好一种选择）：
- 跳过这一轮。
- $a_i$ 的代价获得 $1$ 颗星星。
- $b_i$ 的代价获得 $2$ 颗星星。
- $c_i$ 的代价获得 $3$ 颗星星。
- $d_i$ 的代价获得 $4$ 颗星星。
保证 $0 < 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$
第一行输入数据组数 $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
对于每组数据，输出一个数字表示这组数据的答案。
Sample Input
1 5 10 8 9 10 15 4 6 7 15 4 7 12 15 6 8 10 14 1 8 10 13
Sample Output
28
Hint
依次选择 3,3,0,3,1，代价是 10,7,0,10,1
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）