경기

시간 제한3초메모리 제한128 MB

요약

선수마다 한 바퀴 시간이 매 바퀴 1ms씩 늘지만 p_i바퀴마다 초기화될 때, 같은 시각에 결승선을 통과하는 선수의 최대 수를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 해시맵, 구현, 정수론
정답자: 아직 제출이 없습니다

문제

$K$ 명의 선수가 대회에 참가합니다. 각 선수는 원형 트랙을 정확히 $N$ 바퀴 완주해야 하며, 모든 선수는 출발선에서 동시에 출발합니다.

출발 시점에 모든 선수는 '정상' 컨디션입니다. 달리는 동안 체력이 떨어져 점점 느려지는데, 매 바퀴는 바로 앞 바퀴보다 정확히 1밀리초씩 더 느립니다. 정상 컨디션일 때 선수 $i$ 는 한 바퀴를 ms_i밀리초에 돕니다(ms_i는 양의 정수).

경기 전에 각 선수마다 양의 정수 p_i( $1 \le p_i \le N$ )가 정해집니다. 선수는 p_i바퀴를 완주할 때마다(출발선을 지나는 순간) 에너지 음료를 마셔 다시 정상 컨디션으로 회복하고, 이후 체력은 같은 방식으로 다시 떨어집니다. 음료를 마시는 데 걸리는 시간은 0입니다.

$N$ 바퀴를 도는 동안 각 선수는 출발선을 정확히 $N$ 번 지납니다(마지막 바퀴를 마친 뒤의 통과는 세지만, 맨 처음 출발하는 순간의 통과는 세지 않습니다).

어느 한 순간에 출발선을 동시에 지나는 선수가 최대 몇 명인지 구하세요. 여기서 '동시에'란 경기 시작 후 경과한 밀리초가 서로 같다는 뜻입니다.

입력

첫째 줄에 두 양의 정수 $K$ 와 $N$ 이 공백으로 구분되어 주어집니다. $K$ 는 선수 수, $N$ 은 바퀴 수입니다.

이어서 $K$ 개의 줄에 각 선수의 정보가 한 줄에 하나씩 주어집니다. 각 줄에는 두 양의 정수 ms_i와 p_i가 있으며, ms_i는 선수 $i$ 가 정상 컨디션에서 한 바퀴를 도는 데 걸리는 밀리초, p_i는 에너지 음료를 마셔 정상 컨디션으로 돌아오는 바퀴 주기입니다.

출력

어느 한 순간에 출발선을 동시에 지나는 선수의 최대 수를 정수 하나로 출력합니다.

제한

$2 \le K \le 10000$
$1 \le N \le 1000$
$1 \le ms_i \le 1000000$
$1 \le p_i \le N$

설명

예를 들어 아래 예시에서 선수들은 다음과 같이 각 바퀴를 돕니다. 선수 1은 26, 27, 26밀리초에; 선수 2는 39, 40, 41밀리초에; 선수 3은 45, 45, 45밀리초에; 선수 4는 56, 57, 56밀리초에 각 바퀴를 완주합니다. 따라서 출발선을 지나는 시각(경기 시작 후 누적 밀리초)은 선수 1이 26, 53, 79; 선수 2가 39, 79, 120; 선수 3이 45, 90, 135; 선수 4가 56, 113, 169입니다. 두 명 이상이 함께 출발선을 지나는 경우는 79밀리초에 선수 1과 선수 2가 함께 지나는 순간뿐이므로, 정답은 2입니다.

예제4

예제 1
입력
```
4 3
26 2
39 3
45 1
56 2
```
예상 출력
```
2
```
예제 2
입력
```
5 4
7 1
7 1
7 1
7 1
7 1
```
예상 출력
```
5
```
예제 3
입력
```
2 2
1 1
1000000 1
```
예상 출력
```
1
```
예제 4
입력
```
2 3
10 1
15 1
```
예상 출력
```
2
```