가동 준비가 다른 생산 라인

문제

한 공장은 같은 부품을 만드는 생산 라인 N개를 갖추고 있다. 새 주문을 받은 공장은 시각 0에 모든 생산 라인의 가동 준비를 동시에 시작한다. 생산 라인마다 준비에 걸리는 시간과 부품 하나를 만드는 시간이 다르다. 공장은 완성된 부품을 하나의 보관 구역에 모으며, 주문에 필요한 부품 K개가 모두 모이는 가장 이른 시각을 알아내려고 한다. i번 생산 라인의 준비 시간은 S_i이고 부품 하나의 생산 시간은 T_i다. 이 라인은 시각 S_i에 준비를 마치고 즉시 첫 부품의 생산을 시작한다. 첫 부품은 시각 S_i+T_i에 완성된다. 이후에는 쉬지 않고 다음 부품을 생산하므로 두 번째 부품은 시각 S_i+2T_i에, 세 번째 부품은 시각 S_i+3T_i에 완성된다. 준비가 끝났다는 이유만으로 완성된 부품이 생기는 것은 아니다. 각 생산 라인은 다른 라인과 독립적으로 작동한다. 한 라인에서 준비나 생산을 하는 동안 다른 라인도 동시에 준비하거나 생산할 수 있다. 라인 사이에 작업을 옮기거나 준비 시간을 줄이는 일은 없다. 완성된 부품은 즉시 보관 구역에 들어가며 운반 시간은 따로 필요하지 않다. 부품을 만드는 도중에는 그 부품을 완성 수량에 포함하지 않는다. 어떤 시각에 여러 라인에서 부품이 동시에 완성되면 그 부품들은 모두 해당 시각의 완성 수량에 포함한다. 주문 수량을 넘겨 생산해도 되므로, 한 시각에 부품 수가 K개를 초과하더라도 문제가 되지 않는다. 예를 들어 필요한 마지막 두 부품이 같은 시각에 완성되면 그 시각에 주문 수량을 확보한 것이다. 모든 시간은 시각 0을 기준으로 하는 정수 단위다. 각 라인의 준비 시간과 생산 시간이 주어질 때, 완성된 부품의 총수가 처음으로 K개 이상이 되는 정수 시각을 구한다. 생산 라인은 적어도 하나이고 생산 시간은 양수이므로 답은 항상 존재한다. 여러 라인이 마지막 부품을 함께 완성하더라도 라인 번호를 고를 필요 없이 시각만 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 다음 N개 줄의 i번째 줄에 정수 S_i와 T_i가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 20,000, 1 ≤ K ≤ 1,000,000,000이다. 모든 i에 대해 0 ≤ S_i ≤ 1,000,000, 1 ≤ T_i ≤ 1,000,000이다.

출력

완성된 부품의 총수가 처음으로 K개 이상이 되는 정수 시각을 출력한다.

3 7
0 4
3 2
8 1

10

2 1
5 3
0 10

8

1 1000000000
1000000 1000000

1000000001000000

출처: Devin.KR 자체 제작