경기

$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입니다.