• # 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.

### Task Times solution codechef

• 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.

### Task Times solution codechef

• 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.

## Task Times solution codechef

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


## Task Times solution codechef

1
2
3


### Task Times solution codechef

Test case 11: Chef covers the 1st1st and 2nd2nd topic in 1+1=21+1=2 hours. Both topics belongs to 1st1st subject. He does not cover any topic of the second subject. By doing so, Chef gets 22 +02 ⌈22 ⌉+⌈02 ⌉ =  1 + 0 =1⌈ 1 ⌉+⌈ 0 ⌉=1 marks.

Test case 22: Chef covers the 1st1st topic which belongs to the first subject and 4th4th topic which belongs to the second subject in 1+1=21+1=2 hours. There is no topic from the third subject. So Chef gets 12 +12 ⌈12 ⌉+⌈12 ⌉ =  0.5 + 0.5 =1+1=2⌈ 0.5 ⌉+⌈ 0.5 ⌉=1+1=2 marks.