SOLVE

LATER

Overplay Your Hand

Problem

Editorial

Analytics

Today Alex and Frank are playing a famous game named **"Overplay Your Hand"**.

There are **N** boxes each containing different gifts .The cost price and selling price of **ith** box is **$$c_i$$** and **$$g_i$$** respectively.

Alex starts the game by purchasing a particular box.
According to the game rules Frank can reduce the selling price of the box that Alex purchases, to **0** ( Thereby wasting Alex's money ). As the selling price of the box is reduced to 0, it is waste and thereby forcing Alex to pick another box.

Alex can purchase at most 1 box whose selling price has not been reduced to 0 by Frank

Frank has at most **R** turns. He may refrain from using his turn(i.e does not reduce selling price to 0) thereby allowing Alex to take away the box and the game ends. But he would want to minimize Alex's total profit and Alex's aim is to maximize her total profit ( **selling price of the box - all the previous expenditure in buying the boxes** ).

Alex can quit the game without buying anything. ( Only when there is no chance of getting profit )

You need to help Alex and tell her the maximum profit she can earn when both Alex and Frank use the **optimal** strategy.

Note: Whenever Frank uses his turn, the selling price will reduce to 0 but the buying price will remain same so there is still cost incurred in buying the box ( previous expenditure )

The first line contains **T**, number of testcases.

The second line of input contains two integers **N** and **R** denoting the number of boxes and the maximum number of turns that Frank is allowed respectively.

**N** lines follow where **ith** line contains two integers **G** and **D**, denoting the Selling Price and the Cost price respectively of the **ith** box.

Output the maximum profit that Alex can earn if everyone plays optimally.

**1 <= T <= 100**

**1 <= N <= 200000**

**0 <= R <= 10**

**0 <= G, D <= 10^7**

Setter : Akshat Dua

Explanation

1st Testcase:

Here cost price of all the boxes is same.

Suppose Alex selects **2nd** last box **(S.P. = 50, C.P. = 10)**

**Profit = 50-10 = 40**

Since Frank plays optimally, therefore he will use his turn and reduce the S.P. to **0**.

Now Alex is under loss of **10 dollars**.

Since the game ends only when Alex buys a box whose selling price is not reduced to 0 by Frank or she can't find a way to have net positive profit ( in which case ans is 0 ), she will buy another box.

Obviously she will pick the box that maximizes her profit. In this case the last box **( S.P. = 60, C.P.= 10 ).**

**Profit = 60-10 =50**

As Frank has no other turn left, Alex walks away with a net profit of **(50-10) = 40.**

Here 10 is the cost of purchasing previous box.

You can see that this is the maximum profit she can earn if both of them play optimally.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"2135c41": "/pagelets/problems-hint/algorithm/overplay-your-hand/", "2135c15": "/pagelets/suggested-problems/algorithm/overplay-your-hand/", "2135c2c": "/pagelets/problem-author-tester/algorithm/overplay-your-hand/", "2135c57": "/pagelets/recommended-problems/algorithm/overplay-your-hand/", "2135bf0": "/pagelets/show-submission/algorithm/overplay-your-hand/"}

{}

realtime.hackerearth.com

80

c22657dbab2f2ccffa1af97fcaa6a7fea59a97ce

58a29e5cae2309f04b28

/realtime/pusher/auth/