B - 生徒の成績管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は学校の教務担当として、生徒たちのテスト結果を管理しています。この学校には N 人の生徒がおり、各生徒は 1 から N までの出席番号で識別されます。

先日、複数回にわたって小テストが実施され、合計 M 件の答案が提出されました。各答案には、提出した生徒の出席番号と、その答案の得点（ 0 以上 100 以下の整数）が記録されています。同じ生徒が複数の答案を提出している場合もあれば、 1 件も答案を提出していない生徒（すべての小テストを欠席した生徒）もいる可能性があります。

高橋君は、成績が振るわない生徒を把握するために、以下の基準で「要補習生徒」を特定することにしました。

1 件以上の答案を提出した生徒について、その生徒が提出したすべての答案の得点の算術平均が、あらかじめ定められた基準点 T 未満であるとき、その生徒を「要補習生徒」とみなします。 1 件も答案を提出していない生徒は、判定の対象外とし、要補習生徒には含めません。

高橋君に代わって、要補習生徒の人数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq T \leq 100
  • 1 \leq c_i \leq N (1 \leq i \leq M)
  • 0 \leq s_i \leq 100 (1 \leq i \leq M)
  • 入力はすべて整数である。

入力

N M T
c_1 s_1
c_2 s_2
\vdots
c_M s_M
  • 1 行目には、生徒の人数 N 、答案の総数 M 、基準点 T が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目 (1 \leq i \leq M) には、 i 番目の答案を提出した生徒の出席番号 c_i と、その答案の得点 s_i が、スペース区切りで与えられる。

出力

要補習生徒の人数を 1 行で出力せよ。

入力例 1

5 7 60
1 50
1 40
2 80
2 70
3 55
4 60
4 65

出力例 1

2

入力例 2

8 10 50
1 50
1 50
2 49
2 51
3 0
3 0
4 100
5 30
5 20
6 49

出力例 2

3

入力例 3

10 15 70
1 90
1 80
1 70
2 60
2 50
3 100
4 65
4 70
4 68
6 40
6 30
7 70
8 69
8 71
9 0

出力例 3

4

Score : 300 pts

Problem Statement

Takahashi is in charge of academic affairs at a school and manages the students' test results. There are N students in this school, and each student is identified by a student number from 1 to N.

Recently, multiple quizzes were administered, and a total of M answer sheets were submitted. Each answer sheet records the student number of the student who submitted it and the score of that answer sheet (an integer between 0 and 100, inclusive). It is possible that the same student submitted multiple answer sheets, and there may also be students who did not submit any answer sheets (students who were absent from all quizzes).

To identify students with poor performance, Takahashi decided to determine "students requiring supplementary lessons" based on the following criteria:

For students who submitted at least one answer sheet, if the arithmetic mean of the scores of all answer sheets submitted by that student is strictly less than a predetermined threshold score T, that student is considered a "student requiring supplementary lessons." Students who did not submit any answer sheets are excluded from the evaluation and are not counted as students requiring supplementary lessons.

On behalf of Takahashi, find the number of students requiring supplementary lessons.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq T \leq 100
  • 1 \leq c_i \leq N (1 \leq i \leq M)
  • 0 \leq s_i \leq 100 (1 \leq i \leq M)
  • All input values are integers.

Input

N M T
c_1 s_1
c_2 s_2
\vdots
c_M s_M
  • The first line contains the number of students N, the total number of answer sheets M, and the threshold score T, separated by spaces.
  • The i-th of the following M lines (1 \leq i \leq M) contains the student number c_i of the student who submitted the i-th answer sheet and the score s_i of that answer sheet, separated by spaces.

Output

Output the number of students requiring supplementary lessons in a single line.

Sample Input 1

5 7 60
1 50
1 40
2 80
2 70
3 55
4 60
4 65

Sample Output 1

2

Sample Input 2

8 10 50
1 50
1 50
2 49
2 51
3 0
3 0
4 100
5 30
5 20
6 49

Sample Output 2

3

Sample Input 3

10 15 70
1 90
1 80
1 70
2 60
2 50
3 100
4 65
4 70
4 68
6 40
6 30
7 70
8 69
8 71
9 0

Sample Output 3

4