• # For Solution

Chef’s exam is near. There is a total of MM subjects in his syllabus. Each subject consists of several topics. However, the questions will be set only from NN topics. These topics are numbered 11 through NN. The ithith topic belongs to CthiCith subject and takes TiTi hours to cover.

Chef has only KK hours left before the exam and wants to score the maximum marks. If Chef covers x1x1 number of topics of the 1st1st subject, x2x2 number of topics of the 2nd2nd subject, and so on upto xMxM number of topics of the MthMth subject in the remaining KK hours, he will get a total of x12 +x22 ++xM2 ⌈x12 ⌉+⌈x22 ⌉+⋯+⌈xM2 ⌉ marks in the exam. So Chef chooses the topics optimally. Task Times solution codechef

Determine the maximum possible marks Chef can score in the exam.

Note: x⌈x⌉ : Returns the smallest integer that is greater than or equal to xx (i.e rounds up to the nearest integer). For example, 1.5=2⌈1.5⌉=25=5⌈5⌉=5.

• The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• Each test case contains three lines of input.
• The first line of each test case contains three space-separated integers N,M,KN,M,K.
• The second line contains NN space-separated integers C1,C2,,CNC1,C2,…,CN.
• The third line contains NN space-separated integers T1,T2,,TNT1,T2,…,TN.

### Output Format

For each test case, print a single line containing one integer – the maximum marks Chef can score.

• 1T1041≤T≤104
• 1N1051≤N≤105
• 1MN1≤M≤N
• 1K1091≤K≤109
• 1CiM1≤Ci≤M
• 1Ti1091≤Ti≤109
• Sum of NN over all test cases does not exceed 51055⋅105.

### Sample Input 1

3
3 2 2
1 1 2
1 1 2
4 3 2
1 1 2 2
1 1 2 1
5 3 10
1 1 1 2 3
1 5 2 5 1


1