
79  The 6th Zhejiang Provincial Collegiate Programming Contest  J
JAVAMAN is visiting Dream City and he sees a yard of gold coin trees. There are n trees in the yard. Let's call them tree 1, tree 2 ...and tree n. At the first day, each tree i has a_{i} coins on it (i=1, 2, 3...n). Surprisingly, each tree i can grow b_{i} new coins each day if it is not cut down. From the first day, JAVAMAN can choose to cut down one tree each day to get all the coins on it. Since he can stay in the Dream City for at most m days, he can cut down at most m trees in all and if he decides not to cut one day, he cannot cut any trees later. (In other words, he can only cut down trees for consecutive m or less days from the first day!) Given n, m, a_{i} and b_{i} (i=1, 2, 3...n), calculate the maximum number of gold coins JAVAMAN can get.
Input There are multiple test cases. The first line of input contains an integer T (T <= 200) indicates the number of test cases. Then T test cases follow. Each test case contains 3 lines: The first line of each test case contains 2 positive integers n and m (0 < m <= n <= 250) separated by a space. The second line of each test case contains n positive integers separated by a space, indicating a_{i}. (0 < a_{i} <= 100, i=1, 2, 3...n) The third line of each test case also contains n positive integers separated by a space, indicating b_{i}. (0 < b_{i} <= 100, i=1, 2, 3...n) Output For each test case, output the result in a single line. Sample Input 2 2 1 10 10 1 1 2 2 8 10 2 3 Sample Output 10 21
Hints: Author: CAO, Peng Source: The 6th Zhejiang Provincial Collegiate Programming Contest 