Taxed Editor

Reed Dacht는 집에서 일하는 프리랜서 도서 편집자다. 여러 출판사에서 그에게 원고를 보내며, 편집 의견을 언제까지 돌려받고 싶은지를 마감일로 함께 알려 준다. Reed는 매우 꼼꼼하게 읽기 때문에 한 번에 한 권만 읽고, 이전 책을 다 읽기 전에는 다음 책을 시작하지 않는다. 그는 책을 읽는 속도(하루에 읽는 페이지 수)를 바꿀 수 있지만, 모든 의뢰인에게 공평하기 위해 모든 책에 같은 속도를 쓰기로 했다.

며칠 전 Reed는 많은 편집 의뢰를 받았고 골치가 아프다. 주어진 마감일 안에 모든 책을 다 읽는 방법은 없다고 생각한다. 읽는 속도를 충분히 높이면 다 끝낼 수 있겠지만, 그러면 편집의 정확도가 떨어지고 눈도 몹시 혹사당할 것이다. 그렇다고 속도를 낮추면 너무 많은 편집 작업이 마감일을 넘기게 된다. 그래서 그는 타협하기로 했다. 소수의 책이 마감일을 넘겨도 괜찮으니(그래야 소수의 의뢰인만 화나게 한다) 늦는 책이 그 수를 넘지 않도록 하는 최소한의 하루 페이지 수를 읽기 속도로 정하겠다는 것이다. 그런데 그 속도는 얼마여야 할까? 이제 여러분이 답할 차례다.

입력은 정수 두 개 n m으로 시작한다. n (1 ≤ n ≤ 105)은 편집할 책의 수이고, m (0 ≤ m < n)은 Reed가 늦어도 된다고 허용하는 편집 작업의 수이다. 이어서 n개의 줄이 있고, 각 줄은 책 한 권을 나타낸다. 각 줄에는 정수 두 개 l d가 있는데, l (1 ≤ l ≤ 109)은 책의 길이(페이지 수), d (1 ≤ d ≤ 104)는 그 책의 마감일(마감까지 남은 일수)이다.

늦는 편집 작업이 m개를 넘지 않도록 하는 최소 정수 속도(하루에 읽는 페이지 수)를 출력한다.