반복 재생이 끝나는 시각

문제

한 음악 스트리밍 서비스는 사용자가 만든 재생 목록을 바탕으로 음악 감상 시간을 계산한다. 재생 목록에는 위에서부터 N개의 항목이 있다. i번 항목에는 재생할 곡의 길이 D_i초와 그 곡을 연속해서 재생할 횟수 R_i가 적혀 있다. 서비스는 1번 항목의 곡을 R_1번 모두 재생한 뒤 2번 항목으로 넘어가는 방식으로 마지막 항목까지 처리한다. 곡을 한 번 재생하는 데 걸리는 시간은 언제나 해당 곡의 길이와 같다. 재생 도중 곡을 건너뛰거나 일시 정지하지 않으며, 재생 속도도 바꾸지 않는다. 같은 항목에 적힌 곡을 여러 번 반복할 때도 매번 곡 전체를 처음부터 끝까지 재생한다. 서로 다른 항목에 같은 길이의 곡이 적혀 있어도 각 항목의 재생 횟수는 따로 적용한다. 이 서비스는 한 번의 곡 재생이 끝나고 다음 곡 재생이 시작되기 전에 항상 G초의 안내음을 넣는다. 같은 곡을 반복하는 사이에도 안내음이 들어가고, 한 항목의 마지막 재생에서 다음 항목의 첫 재생으로 넘어갈 때도 안내음이 들어간다. 안내음의 길이는 곡이나 항목에 관계없이 같다. G가 0이면 안내음으로 추가되는 시간은 없다. 첫 번째 곡을 시작하기 전에는 안내음이 없으며, 마지막 항목의 마지막 재생이 끝난 뒤에도 안내음을 넣지 않는다. 따라서 전체 목록에서 곡을 단 한 번만 재생한다면 안내음은 한 번도 들어가지 않는다. 첫 번째 곡이 시작되는 순간부터 마지막 곡이 끝나는 순간까지를 전체 감상 시간으로 정한다. 모든 항목의 곡 길이와 반복 횟수가 주어졌을 때, 안내음까지 포함한 전체 감상 시간이 몇 초인지 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 G가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ G ≤ 30이다.
다음 N개의 줄 중 i번째 줄에 정수 D_i와 R_i가 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ D_i ≤ 600, 1 ≤ R_i ≤ 1,000이다.

출력

안내음까지 포함한 전체 감상 시간을 초 단위의 정수로 한 줄에 출력한다. 단위는 출력하지 않는다.

2 3
120 2
95 1

341

1 30
247 1

247

3 0
60 3
45 2
100 1

370

출처: Devin.KR 자체 제작