#P17739. [ICPC 2019 Xuzhou R] Interesting game
[ICPC 2019 Xuzhou R] Interesting game
Problem Description
Amy and Bob are good friends. Today they want to play a game.
Here is the process about it:
- There are items in total. The item has points to Amy and points to Bob.
- Bob takes items out of the game, so neither of them can pick these items. ()
- Amy picks one item first, assume she takes item, then she gets points.
- Bob picks one item, assume he takes item, then he gets points.
- The game ends.
Now they are wondering what is the value of if they play optimally.
(Amy wants to be maximum, Bob wants to be minimum)
Please help them calculate the value when is in .
Input Format
The first line contains one integer, () --- the number of items.
Each of the next lines contains two integers, and ()--- meaning the item has value to Amy and value to Bob.
Output Format
Output integers, each of them in one line.
The line is the value of when Bob bans exactly items ()
5
2 2
3 2
4 4
5 6
6 6
0
0
0
0
3
4 100
5 98
1 100
-95
-96