28448번 - 광기의 PS

문제

승민이는 요즘 PS에 빠져 있다. 인생을 PS에 바쳐버린 승민이는 풀겠다고 마음먹은 문제는 몇 시간이고 며칠이고 붙잡고 있는다. 그러나 그럴 때마다 승민이의 정신은 점점 광기에 물들고 있다. 광기가 너무 많이 쌓이면 문제를 해결하는 데 방해가 되기 때문에, 승민이는 적절한 시기에 효율적으로 휴식을 취하려고 한다.

난이도 $K$인 문제를 $T$시간이 걸려 푸는 동안, 1시간마다 광기가 $K$ 쌓인다.

문제를 해결했다면, 광기는 $min(KT, 5K)$만큼 해소된다.

휴식을 취하면, 1시간마다 광기가 1ドル$만큼 해소된다. 단, 광기는 0 미만으로 떨어지지 않는다.

광기가 너무 많이 쌓이는 걸 방지하기 위해, 승민이는 $L$ 이하로 광기를 유지하려고 한다. 이 조건을 만족하면서 주어진 문제들을 모두 푸는 최소 시간을 계산하자.

단, 어떤 문제를 푸는 도중에는 휴식할 수 없고, 문제를 다 풀고 다른 문제로 이동해야 한다. 또한, 승민이는 문제를 동시에 해결할 수 없다.

입력

첫 번째 줄에 문제의 개수 $N$ (1ドル \leq N \leq 1,000円,000円$)과 광기의 최대 제한 $L$ (1ドル \leq L \leq 10^9, L$은 정수)이 주어진다.

두 번째 줄부터 난이도 $K_i$ (1ドル \leq K_i \leq 100,000,円 K_i$는 정수), 푸는 시간 $T_i$ (1ドル \leq T_i \leq 100,000,円 T_i$는 정수), (1ドル \leq K_iT_i \leq L$)이 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 주어진 문제들을 모두 푸는 최소 시간을 출력하자.

제한

힌트