Informatica Online Judge

  아이스크림과 의문의 약 [0201 / 00C9]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 35   Total Tried : 45


The Champion of this Problem (C++) : gs18080 - ms / 627byte
My Best Submission (C++) : N/A

[]

Background

GSHS에는 N명의 학생이 있다.

기말고사가 끝난 어느날 GSHS의 선생님들이 학생들에게 줄 아이스크림을 K개 사왔다.

그런데 마음씨가 나쁜 어떤 선생님이 N명의 학생들을 1학기 성적순으로 한줄로 세웠다.

성적이 높은사람부터 각자가 먹을 수 있는 한도 내에서는 아이스크림을 마음껏 먹고 다음사람에게 아이스크림을 먹을 기회를 주라고 했는데(꼴지인 학생 다음에는 1등인 학생이 아이스크림을 먹는다.),

하나도 먹지 않으면 벌점을 주겠다고 했다. 그런데 갑자기 sutekine선생님이 K개의 아이스크림중 마지막 한개에 성분을 알 수 없는 미지의 약을 넣었다.

그리고 그 사실을 모든 학생들에게 알렸다. 이 때, 과연 1학기 성적이 몇등인 학생이 그 미지의 약을 먹을까?

단, 각 학생들은 GSHS의 학생답게 매우 논리적이고 천재적으로 자신의 목표를 위해 최선을 다해 아이스크림을 먹는다.

또한, 각 학생들은 N명의 학생들을 자기가 싫어하는 순서대로 미지의 약을 먹이고 싶어 하는데 GSHS의 학생답게 똘끼가 넘쳐서 자기 자신을 싫어하는 학생들이 없다고 말할 수 없다.

Input

첫번째 줄에 두 자연수 N(<=100), K(<=10000)이 입력된다.
두번째 줄~N+1번째 줄에는 자연수 Pi,Xi1,Xi2,...,XiN이 입력된다. Pi(<=25)는 한꺼번에 먹을수 있는 아이스크림의 최대개수, Xik는 k번째로 싫어하는 학생의 1학기 등수이다.

Output

첫번째 줄에 미지의 약을 먹게되는 학생의 1학기 등수를 출력한다.

IO Example

입력
3 5
3 3 2 1
2 1 3 2
1 1 2 3

출력
3



설명>
1등이 3개의 아이스크림을 먹고, 2등이 1개의 아이스크림을 먹고, 3등이 1개의 아이스크림을 먹는다.


힌트>
시간관리에 주의할 것.


출제 : 한민기(GSHS 26th)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]