A - Figure Skating Qualifying Round Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、フィギュアスケートの地区予選大会の運営スタッフとして働いています。

この大会では N 人の選手が演技を披露し、それぞれの選手は M 人の審査員から採点を受けます。選手 i（1 \leq i \leq N）が審査員 j（1 \leq j \leq M）から受け取る得点は整数 S_{i,j} です。

フィギュアスケートの採点では、極端な採点の影響を抑えるため、各選手の最終得点は以下のように計算されます。

  • M \geq 3 の場合：選手が受け取った M 個の得点の中から、最も高い得点 1 つと最も低い得点 1 つを除きます。同じ値の得点が複数あっても、除くのはそれぞれ 1 つずつだけです。残りの M - 2 個の得点の平均値（合計を M - 2 で割った値）を求め、小数点以下を切り捨てた整数を最終得点とします。
  • M = 1 または M = 2 の場合：得点を除外すると残りが 0 個以下になってしまうため、除外は行いません。M 個すべての得点の平均値（合計を M で割った値）を求め、小数点以下を切り捨てた整数を最終得点とします。

ここで「小数点以下を切り捨てる」とは、その値を超えない最大の整数をとる操作（床関数 \lfloor \cdot \rfloor）を意味します。なお、得点はすべて 0 以上であるため、最終得点も 0 以上の整数となります。

本戦への出場資格を得るためには、最終得点が基準点 K 点以上である必要があります。最終得点が K 点未満の選手は予選落ちとなります。

高橋君に代わって、予選落ちとなる選手の人数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 100
  • 0 \leq K \leq 100
  • 0 \leq S_{i,j} \leq 100 (1 \leq i \leq N, 1 \leq j \leq M)
  • 入力はすべて整数

入力

N M K
S_{1,1} S_{1,2} \ldots S_{1,M}
S_{2,1} S_{2,2} \ldots S_{2,M}
\vdots
S_{N,1} S_{N,2} \ldots S_{N,M}
  • 1 行目には、参加選手数を表す整数 N、審査員数を表す整数 M、基準点を表す整数 K が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目には、各選手が各審査員から受け取る得点が与えられる。
  • 1 + i 行目（1 \leq i \leq N）には、選手 i が審査員 1, 2, \ldots, M から受け取る得点 S_{i,1}, S_{i,2}, \ldots, S_{i,M} がスペース区切りで与えられる。

出力

予選落ちとなる選手の人数を 1 行で出力してください。

入力例 1

3 5 70
80 75 60 90 85
50 55 60 65 70
100 100 100 100 100

出力例 1

1

入力例 2

4 2 50
60 40
100 0
49 50
55 55

出力例 2

1

入力例 3

5 7 75
80 85 90 70 75 88 92
60 65 70 55 58 62 68
100 99 98 97 96 95 94
74 74 74 74 74 74 74
75 75 75 75 75 75 75

出力例 3

2

Score : 266 pts

Problem Statement

Takahashi is working as an operations staff member for a figure skating regional qualifying competition.

In this competition, N athletes perform, and each athlete is scored by M judges. The score that athlete i (1 \leq i \leq N) receives from judge j (1 \leq j \leq M) is an integer S_{i,j}.

In figure skating scoring, to reduce the influence of extreme scores, each athlete's final score is calculated as follows:

  • When M \geq 3: From the M scores the athlete received, the single highest score and the single lowest score are removed. Even if there are multiple scores with the same value, only one of each is removed. The average of the remaining M - 2 scores (the sum divided by M - 2) is computed, and the integer obtained by truncating the decimal part is the final score.
  • When M = 1 or M = 2: Since removing scores would leave 0 or fewer remaining, no scores are removed. The average of all M scores (the sum divided by M) is computed, and the integer obtained by truncating the decimal part is the final score.

Here, "truncating the decimal part" means taking the largest integer that does not exceed the value (the floor function \lfloor \cdot \rfloor). Note that since all scores are 0 or greater, the final score is also a non-negative integer.

To qualify for the main competition, an athlete's final score must be at least the threshold score of K points. Athletes whose final score is less than K points are eliminated in the qualifying round.

On behalf of Takahashi, determine the number of athletes who are eliminated in the qualifying round.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 100
  • 0 \leq K \leq 100
  • 0 \leq S_{i,j} \leq 100 (1 \leq i \leq N, 1 \leq j \leq M)
  • All input values are integers

Input

N M K
S_{1,1} S_{1,2} \ldots S_{1,M}
S_{2,1} S_{2,2} \ldots S_{2,M}
\vdots
S_{N,1} S_{N,2} \ldots S_{N,M}
  • The first line contains three space-separated integers: N representing the number of athletes, M representing the number of judges, and K representing the threshold score.
  • From the 2nd line to the (N + 1)-th line, the scores each athlete receives from each judge are given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the scores S_{i,1}, S_{i,2}, \ldots, S_{i,M} that athlete i receives from judges 1, 2, \ldots, M, separated by spaces.

Output

Output the number of athletes who are eliminated in the qualifying round, in a single line.

Sample Input 1

3 5 70
80 75 60 90 85
50 55 60 65 70
100 100 100 100 100

Sample Output 1

1

Sample Input 2

4 2 50
60 40
100 0
49 50
55 55

Sample Output 2

1

Sample Input 3

5 7 75
80 85 90 70 75 88 92
60 65 70 55 58 62 68
100 99 98 97 96 95 94
74 74 74 74 74 74 74
75 75 75 75 75 75 75

Sample Output 3

2