Abdulrahman has OCD so he is so careful with how clean and neat his codes are, so naturally he likes implementation and data structure problem, so Ahmad decided to give him one. Please don't disappoint him with your code for this data structures problem.
You're given two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$. You're also given an integer $$$k$$$, the value of any sequence $$$(1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n)$$$ is $$$\sum_{j=1}^{k}{a_{i_j}} \space - \max\limits_{1 \leq j \leq k}b_{i_j}$$$.
What's the maximum value of any sequence of length $$$k$$$?
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
For each test case, the first line contains two integers $$$n$$$ $$$k$$$ $$$(1 \leq k \leq n \leq 2\cdot 10^5)$$$.
The next $$$n$$$ lines each contains two integers $$$a_i$$$ $$$b_i$$$ $$$(1 \leq a_i \leq 10^9; -10^{15} \leq b_i \leq 10^{15})$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, print one integer, the maximum value of any sequence of length k.
33 13 25 64 13 23 25 64 13 33 25 64 1
3 5 6
13 21 41 41 4
-2
| JPC 4.0 |
|---|
| Finished |
