몬스터를 처치하자!
면접 대비시간 제한2초메모리 제한512 MB
스킬은 사용에 1초가 걸리고 1초 뒤에 피해를 입히며, 사용 시점부터 재사용 대기시간이 흐른다. 몬스터의 HP를 0으로 만드는 최소 시간을 구한다.
문제
가장 빠른 시간 안에 몬스터를 처치하려고 한다. 사용할 수 있는 스킬은 N개 있고, 각 스킬은 사용하는 데 1초가 걸리며 사용을 시작한 지 1초 후에 몬스터에게 일정 대미지를 입힌다. 여러 스킬을 동시에 사용할 수는 없다.
각 스킬에는 저마다의 대기 시간과 대미지가 있다. 대기 시간은 스킬을 사용하기 시작한 순간부터 센다.
예를 들어 현재 시각이 t = 0이고, 대기 시간이 10초, 대미지가 10인 스킬을 체력이 100인 몬스터에게 사용했다고 하자. 그러면 t = 1일 때 몬스터의 체력이 90으로 줄어들고, 같은 스킬은 t = 10일 때부터 다시 사용할 수 있다.
입력
첫 번째 줄에는 스킬 개수 N(1 ≤ N ≤ 5)과 몬스터의 체력(HP)을 나타내는 정수(1 ≤ HP ≤ 100000)가 주어진다.
두 번째 줄부터는 줄마다 스킬의 대기 시간을 초 단위로 나타내는 정수 C(1 ≤ C ≤ 10)와 스킬의 대미지를 나타내는 정수 D(HP/10 ≤ D ≤ HP)가 공백을 두고 주어진다. 모든 스킬의 대기 시간은 다르며, 모든 D의 합은 HP보다 작다.
출력
몬스터를 처치하는 데 걸리는 최소 시간을 출력한다.