Hide

Problem F
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 n1 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 (1k105) and n (1n105), 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 (2011y2011+n1) and p (0p2311). These are his year of entry into the tournament and his strength, respectively.

Then follow n+k2 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 n1 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
Hide

Please log in to submit a solution to this problem

Log in