You are playing a video game of N different levels. Initially, you are at level 1 and have at most M minutes of free time to play the game. Playing the i′th level gives you an A[i] amount of happiness, and it takes V[i] minutes to play, where A and V are given in the form of an array with N elements.
Additionally, you have K skips, where 1 skip allows you to skip your current level and go directly to the next level. If you skip a level, you won’t receive happiness for that level. Also, you won’t lose any minutes while skipping the level.
If you are currently at the i′th level, you can do any of the following three things:
If you try to get to the next level (N+1) when you are at level N, the game breaks, and you won’t get any other amount of happiness. Your task is to find the maximum amount of happiness you can get by playing at most M minutes of the video game.
Input Format:
Output Format:
For each test case, print the maximum amount of happiness you can achieve by playing the game for at most M minutes.
Constraints:
1≤T≤10
1≤N,M≤100
0≤K≤20
1≤A[i]≤100
1≤V[i]≤20
For test case 1:
You can play level 1, choose to go to the next level and play level 2. So, you will get a total of 4+2 = 6 happiness, and the time taken is 2+1 = 3, which doesn’t exceed M. Note that it is not compulsory to use all the given skips. Here we haven’t used them. Hence, the answer is 6.
For test case 2:
We can achieve 8 amounts of happiness if we play in the following manner:
For test case 3:
We can play the first, second, and third levels once and get 3 amounts of happiness. Playing the same level again won’t increase happiness in this case.