Page not loading? Try clicking here.
Placeholder

#8236

케이크 프로그래밍 대회 1s 128MB

Problems

오늘은 아주 중요한 날이다: 권수쌤이 프로그래밍 대회를 주최하고 있다. 놀랍게도 모든 학생들이 참가하여 참가율이 100%에 달했는데, 이유를 알아보니 권수쌤이 대회에서 자신을 이기는 모든 학생에게 케이크를 구워주겠다고 약속했기 때문이다. 대회가 끝난 후, 권수쌤은 점수판을 받게 된다. 권수쌤은 시간이 부족하다: 케이크를 구우는 일 외에도 시험을 채점해야 하기 때문이다. 따라서 권수쌤은 자신이 대회에서 몇 명의 학생에게 졌는지를 계산할 수 있는 프로그램이 필요하다.

대회는 P개의 문제로 구성되어 있으며, S-1명의 학생들은 가능한 한 빠르게 문제를 풀어야 한다. 한 사람이 다른 사람을 이겼다고 할 수 있는 경우는 첫 번째 사람이 푼 문제의 개수가 두 번째 사람보다 더 많을 때이다. 만약 푼 문제의 개수가 같다면, 더 적은 시간으로 문제를 푼 사람이 이겼다고 할 수 있다. 권수쌤은 자신과 동일한 개수의 문제를 풀고 동일한 시간으로 문제를 푼 학생들에게도 케이크를 구워줄 의향이 있다.


Input

한 줄에 두 정수 S와 P가 주어진다. (2 \leq S, P \leq 1000), 각각 참가하는 사람의 수(권수쌤 포함)와 프로그래밍 문제의 수를 의미한다.

다음 줄에는 P개의 정수가 주어지며, 권수쌤 결과를 나타낸다.

그리고 이어서 S-1개의 줄에 P개의 정수로 각 학생들의 결과가 주어진다.

각 결과는 해당 학생이 문제를 풀지 못했음을 나타내는 X 또는 해당 학생이 문제를 푸는 데 걸린 시간(분)을 나타내는 정수 M으로 주어진다. (1 \leq M \leq 10^6)


Output

권수쌤이 케이크를 구워줘야 할 학생의 수를 출력한다.


Subtask

# Score Condition
#130

2 \le S,P \le 10

#270

추가 제약 조건 없음


Example #1

5 5
40 X 10 30 20
X X 20 50 40
50 40 20 30 10
X X 30 X 50
X 30 5 40 20
2

위 입력에 해당하는 스코어보드의 모습이다. 각 칸에는 각 문제에서 얻은 점수와 그 아래 괄호안에 해당 문제를 푸는데 소모된 시간이 적혀있다.


Example #2

4 4
4 5 6 X
4 5 X 5
4 X 5 6
X 4 5 7
2


Source

Delft University of Technology Freshmen Programming Contest 2022 C번
You must sign in to write code.