Problem Description
We are familiar with the skill tree in different game. If you wanna get a new skill, you must get some base skill first. Let's simplify the problem: There is a inverse-triangle skill tree, with each node assigned a power value. If you wanna get a skill, you must get its left-upper and right-upper skill first. for example:
1 2 3 4 1 7 1 2 2 9 You must get the skill with power 2 and 3 to get the skill with power 7. Because of the lack of skill point, we could only get M skills. What's the maximum power value we can get?
Input
The first line is the number of testcase T (T≤20). Each case start with two numbers N (N≤47) and M (M≤474), represent the size of skill tree and skill point. Next N line, for each line i, there're N-i+1 numbers which represent the skill tree. Each number will between 0 and 1000.
Output
Output case number first, then the answer.
Sample Input14 51 1 1 11 2 11 11Sample OutputCase 1: 6
We are familiar with the skill tree in different game. If you wanna get a new skill, you must get some base skill first. Let's simplify the problem: There is a inverse-triangle skill tree, with each node assigned a power value. If you wanna get a skill, you must get its left-upper and right-upper skill first. for example:
1 2 3 4 1 7 1 2 2 9 You must get the skill with power 2 and 3 to get the skill with power 7. Because of the lack of skill point, we could only get M skills. What's the maximum power value we can get?
Input
The first line is the number of testcase T (T≤20). Each case start with two numbers N (N≤47) and M (M≤474), represent the size of skill tree and skill point. Next N line, for each line i, there're N-i+1 numbers which represent the skill tree. Each number will between 0 and 1000.
Output
Output case number first, then the answer.
Sample Input14 51 1 1 11 2 11 11Sample OutputCase 1: 6
