아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

숲의 왕들

시간 제한1초메모리 제한128 MB

요약
경쟁하는 모든 무스의 힘과 등장 연도를 보고 Karl-Algtav가 우승하는 연도를 구하거나 알 수 없으면 unknown을 출력한다.
난이도

보통10점 중 7점

유형
힙, 시뮬레이션, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

모든 무스(큰사슴)는 숲의 왕이지만, 당신의 새 무스 친구 칼-엘그타브(Karl-Älgtav)는 그중에서도 특별합니다. 발효된 블루베리를 좋아한다는 점도 그렇고, 그가 속한 무리 때문이기도 합니다.

이 무리는 매년 토너먼트를 열어 그 해의 우두머리 무스(알파 무스)를 정합니다. 우승한 무스는 모든 암컷 새끼와 짝짓기를 한 뒤 무리를 영영 떠납니다. 경쟁자 집단의 크기는 해마다 그대로 유지됩니다. 즉, 떠난 우두머리의 자리는 다음 토너먼트가 열리기 전에 정확히 한 마리의 새로운 무스로 채워집니다.

칼-엘그타브는 언제쯤 자신의 차례가 올지 궁금해합니다. 그는 앞으로 n−1n-1년 동안 함께 경쟁할 다른 모든 수컷 무스의 힘과 토너먼트 참가 연도를 당신에게 알려 주었습니다. 매년 힘이 가장 센 무스가 그 해의 토너먼트에서 우승한다고 할 때, 칼-엘그타브가 우두머리 무스가 되는 연도를 구하세요.

입력

첫째 줄에는 공백으로 구분된 두 정수 kk (1≤k≤1051 \le k \le 10^5)와 nn (1≤n≤1051 \le n \le 10^5)이 주어집니다. 각각 토너먼트 참가 집단의 크기와, 충분한 정보가 주어진 연도의 수를 의미합니다.

다음 줄에는 칼-엘그타브를 나타내는 두 정수 yy (2011≤y≤2011+n−12011 \le y \le 2011 + n - 1)와 pp (0≤p≤231−10 \le p \le 2^{31} - 1)가 주어집니다. 각각 그의 토너먼트 참가 연도와 힘입니다.

이어지는 n+k−2n + k - 2개의 줄에는 다른 무스들이 같은 형식으로, 즉 참가 연도와 힘이 주어집니다.

무스들 중 정확히 kk마리는 참가 연도가 20112011이고, 나머지 n−1n - 1마리는 모두 서로 다른 참가 연도를 가집니다. 또한 모든 무스의 힘은 서로 다릅니다.

출력

칼-엘그타브가 토너먼트에서 우승하는 연도를 출력합니다. 주어진 정보만으로는 이를 결정할 수 없다면 unknown을 출력합니다.

예제2

  1. 예제 1

    입력
    2 4
    2013 2
    2011 1
    2011 3
    2014 4
    2012 6
    
    예상 출력
    2013
    
  2. 예제 2

    입력
    2 4
    2011 1
    2013 2
    2012 4
    2011 5
    2014 3
    
    예상 출력
    unknown