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:

Skip the current level if you have any skips left, and go to the \(i+1\) level.
Play the current level and go to the next level, \(i+1\).
Play the current level and choose to remain on the same level. But the happiness you get next time is half of what you get now. Let’s say you got \(X\) amount of happiness by playing the current level. If you stay on the same level, you will get \(\lfloor \frac{X}{2} \rfloor\) amount of happiness next time. \(\lfloor \frac{X}{Y} \rfloor\) means the value of \(X / Y\) rounded down to the nearest integer.

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:

The first line contains a single integer \(T\) denoting the number of test cases, then the test case follows.
The first line of each test case contains three single space-separated integers, \(N\), \(M\), and \(K\).
The second line of each test case contains \(N\) single space-separated integers, denoting \(A\).
The third line of each test case contains \(N\) single space-separated integers, denoting \(V\).

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\)