18712번 - Ice-cream Knapsack 다국어

문제

There is a wonderful ice-cream shop that contains N ice-creams, such that each ice-cream is represented by two numbers C_i and H_i denoting the number of calories and the happiness value, respectively.

You want to buy exactly K ice-creams such that the calories of the densest ice-cream (the one with most calories) are as minimal as possible. If there is more than one way to do that, you want to maximize the total happiness of the ice-creams you will buy, that is the sum of the happiness values of the chosen ice-creams.

입력

The first line of the input contains a single integer T specifying the number of test cases.

Each test case begins with a line containing two integers N and K (1 ≤ K ≤ N ≤ 10⁵), in which N is the number of ice-creams in the shop, and K is the number of ice-creams you want to buy.

Then a line follows containing N integers C₁, · · · , C_N (0 ≤ C_i ≤ 10⁹), in which C_i is the number of calories in the i^th ice-cream. Then a line follows containing N integers H₁, · · · , H_N (0 ≤ H_i ≤ 10⁹), in which H_i is the happiness value of the i^th ice-cream.

출력

For each test case, print a single line containing two space-separated integers representing the calories of the densest ice-cream you will buy and the total happiness of the ice-creams you will buy, respectively.

Remember that your goal is to buy K ice-creams such that the calories of the densest ice-cream (the one with most calories) are as minimal as possible. If there is more than one way to do that, you want to maximize the total happiness of the ice-creams you will buy.

제한

힌트