CF1996F Bomb

Sparkle gives you two arrays $ a $ and $ b $ of length $ n $ . Initially, your score is $ 0 $ . In one operation, you can choose an integer $ i $ and add $ a_i $ to your score. Then, you must set $ a_i $ = $ \max(0, a_i - b_i) $ . You only have time to perform $ k $ operations before Sparkle sets off a nuclear bomb! What is the maximum score you can acquire after $ k $ operations?

The first line contains $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains $ n $ and $ k $ ( $ 1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9 $ ) — the length of the arrays and the number of operations you can perform. The following line contains $ n $ integers $ a_1, a_2, ... a_n $ ( $ 1 \leq a_i \leq 10^9 $ ). The following line contains $ n $ integers $ b_1, b_2, ... b_n $ ( $ 1 \leq b_i \leq 10^9 $ ). It is guaranteed that the sum of $ n $ for all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output an integer, the maximum score you can acquire after $ k $ operations.