통학 버스

통학 버스는 학생을 최대 M명까지 태울 수 있다. 버스는 매일 정해진 노선을 따라 학생들을 학교로 데려가며, 노선에는 여러 정류장이 있다. 각 정류장에서 버스에 빈자리가 있으면 학생들이 탄다. 버스는 아직 도착하지 않은 학생을 정류장에서 기다릴 수도 있다. 버스가 한 정류장에서 다음 정류장까지 이동하는 시간과 각 학생이 자기 정류장에 도착하는 시각이 주어진다. 버스는 시각 0에 시작 정류장에 도착한다. 학생이 버스에 타는 데 걸리는 시간은 0이다.

프로그램 school을 작성하여, 버스가 M명의 학생을 태우거나 전체 학생 수가 M보다 작으면 모든 학생을 태운 상태로 시작 정류장에서 학교까지 이동하는 시간의 최솟값을 구하라.

표준 입력의 첫째 줄에 두 정수 N과 M이 주어진다. N은 정류장 수, M은 버스의 좌석 수이다. 다음 N개 줄 각각에는 ti, Ki, 그리고 Ki개의 정수가 주어진다. ti는 다음 정류장까지 이동하는 시간(마지막 정류장에서는 학교까지 이동하는 시간)이고, Ki는 그 정류장에서 기다리는 학생 수이며, 이어서 학생들이 도착하는 시각이 감소하지 않는 순서로 주어진다. 모든 수는 정수이다.

표준 출력의 한 줄에 하나의 정수를 출력한다. 버스가 만석으로 도착하거나, 전체 학생 수가 M보다 작으면 모든 학생을 태우고 도착할 때 시작 정류장에서 학교까지 이동하는 시간의 최솟값이다.

• 2 ≤ N*M ≤ 10^6