Make Them Equal solution codeforces- You have an array of integers aa of size nn. Initially, all elements of the array are equal to 11. You can perform the following operation: choose two integers ii (1≤i≤n1≤i≤n) and xx (x>0x>0), and then increase the value of aiai by ⌊aix⌋⌊aix⌋ (i.e. make ai=ai+⌊aix⌋ai=ai+⌊aix⌋). After performing all operations, you will receive cici coins for all such ii that ai=biai=bi. Your task is to determine the maximum number of coins that you can receive by performing no more than kk operations.

Make Them Equal solution codeforces

You have an array of integers aa of size nn. Initially, all elements of the array are equal to 11. You can perform the following operation: choose two integers ii (1≤i≤n1≤i≤n) and xx (x>0x>0), and then increase the value of aiai by ⌊aix⌋⌊aix⌋ (i.e. make ai=ai+⌊aix⌋ai=ai+⌊aix⌋).

After performing all operations, you will receive cici coins for all such ii that ai=biai=bi.

Your task is to determine the maximum number of coins that you can receive by performing no more than kk operations.

Input Make Them Equal solution codeforces

The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases.

The first line of each test case contains two integers nn and kk (1≤n≤103;0≤k≤1061≤n≤103;0≤k≤106) — the size of the array and the maximum number of operations, respectively.

The second line contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1031≤bi≤103).

The third line contains nn integers c1,c2,…,cnc1,c2,…,cn (1≤ci≤1061≤ci≤106).

The sum of nn  over all test cases does not exceed 103103.

Output Make Them Equal solution codeforces

For each test cas e, print one integer — the maximum number of coins that you can get by performing no more than kk operations.

Example

input

Copy
4
4 4
1 7 5 2
2 6 5 2
3 0
3 5 2
5 4 7
5 9
5 2 5 6 3
5 9 1 9 7
6 14
11 4 6 2 8 16
43 45 9 41 15 38

output

Copy Make Them Equal solution codeforces
9
0
30
167

Leave a Comment

Your email address will not be published.