Hide

Problem D
Knigs of the Forest

/problems/knigsoftheforest/file/statement/en/img-0001.jpg

All moose are knigs of the forest, but your latest moose-friend, Karl-Älgtav, is more interesting than most. In part because of his fondness of fermented blueberries, and in part because of the tribe he lives in. Each year his tribe holds a tournament to determine that year’s alpha-moose. The winner gets to lead the tribe for a year, and then permanently leaves the tribe. The pool of contenders stays constant over the years, apart from the old alpha-moose being replaced by a newcomer in each tournament.

Karl-Älgtav has recently begun to wonder when it will be his turn to win, and has asked you to help him determine this. He has supplied a list of the strength of each of the other moose in his tribe that will compete during the next $n - 1$ years, along with their time of entry into the tournament. Assuming that the winner each year is the moose with greatest strength, determine when Karl-Älgtav becomes the alpha-moose.

Input

The first line of input contains two space separated integers $k$ ($1 \leq k \leq 10^5$) and $n$ ($1 \leq n \leq 10^5$), denoting the size of the tournament pool and the number of years for which you have been supplied sufficient information.

Next is a single line describing Karl-Älgtav, containing the two integers $y$ ($2011 \leq y \leq 2011 + n - 1$) and $p$ ($0 \leq p \leq 2^{31}-1$). These are his year of entry into the tournament and his strength, respectively.

Then follow $n + k - 2$ lines describing each of the other moose, in the same format as for Karl-Älgtav.

Note that exactly $k$ of the moose will have $2011$ as their year of entry, and that the remaining $n-1$ moose will have unique years of entry.

You may assume that the strength of each moose is unique.

Output

The year Karl-Älgtav wins the tournament, or unknown if the given data is insufficient for determining this.

Sample Input 1 Sample Output 1
2 4
2013 2
2011 1
2011 3
2014 4
2012 6
2013
Sample Input 2 Sample Output 2
2 4
2011 1
2013 2
2012 4
2011 5
2014 3
unknown

Please log in to submit a solution to this problem

Log in