요새 방어

포위된 요새의 성벽은 1번부터 $n$번까지 번호가 붙은 $n$개의 구간으로 이루어져 있다. 첩보에 따르면 다음 공격에서 적은 $i$번 구간을 공격할 병사 $a_i$명을 보낸다. 요새를 방어하기 위해 성벽의 구간들에 $s$명의 방어병을 배치한다.

성벽의 구간마다 방어 시설의 품질이 달라 방어 효율도 다르다. $i$번 구간의 방어병 한 명은 적 $k_i$명의 공격을 막아낼 수 있다.

$i$번 구간에 방어병 $x_i$명을 보냈다고 하자. 그러면 적의 수가 $x_i \cdot k_i$를 넘지 않으면 이 구간에서는 적이 한 명도 요새로 뚫고 들어오지 못한다. 그렇지 않으면 $a_i - x_i \cdot k_i$명의 적이 요새로 뚫고 들어온다.

방어병을 구간에 배치해 총수가 $s$가 되게 하면서 요새로 뚫고 들어오는 적의 수를 최소로 만드는 프로그램을 작성하라.

첫째 줄에는 성벽의 구간 수 $n$과 요새의 방어병 수 $s$가 주어진다 ($1 \leq n \leq 100\,000$; $1 \leq s \leq 10^9$).

다음 $n$개의 줄에는 정수 $a_i, k_i$가 한 줄에 하나씩 주어진다. $a_i$는 $i$번 구간을 공격하는 적의 총수, $k_i$는 이 구간의 방어병 한 명이 막아낼 수 있는 적의 수이다 ($1 \leq a_i, k_i \leq 10^9$).

요새로 뚫고 들어오는 적의 최소 수를 나타내는 정수 하나를 출력한다.

첫 번째 테스트에서 방어병 10명을 전부 하나뿐인 구간에 배치하면 모든 적을 막아낼 수 있어 아무도 요새로 들어오지 못한다. 두 번째 예에서는 예를 들어 방어병 두 명을 첫 번째 구간에, 한 명을 세 번째 구간에 보내면 된다.