Bicycle Track Race

Interview

Time limit1sMemory limit1024 MB

Summary

Given each racer's time per lap and the race length in laps, count the racers who are never lapped and finish the race.

Level: Medium4 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

In the Kingdom of Bits, a bicycle track race takes place. All cyclists start at the same time and ride $N$ laps. When one racer laps another, the lapped racer drops out of the race. If a racer crosses the finish line and laps a rival at that moment, the lapped rival also drops out. Given the time each cyclist needs to complete one lap of the track and the length of the race in laps, find how many participants are not lapped and finish the race.

Input

The first line contains three natural numbers separated by spaces:

$N$ : number of racers;
$M$ : length of the race in laps;
$L$ : length of one lap of the track in meters.

Each of the next $N$ lines contains $T_i$ , the number of seconds one racer needs to complete one lap of the track. $T_i$ is a natural number.

Output

Print the number of racers who were not lapped and finished the race.

Constraints

$2 \le N, M, L, T_i \le 10\,000$

Examples2

Example 1
Input
```
2 2 200
10
20
```
Expected output
```
1
```
Example 2
Input
```
3 2 20
2
3
5
```
Expected output
```
2
```