[문제 요약]여러개의 블록을 쌓아서 소들이 우주로 가려고 한다.

그들은 K ( 1 <= K <= 400 ) 종류의 블록을 가지고 있고 , i 번째 블록 은 높이 h_i ( 1 <= h_i <= 100 ) 와 개수 c_i( 1 <= c_i <= 10 ) 을 가지고 있다. 우주광선의 영향으로 i 번째 타입의 어떤 블록도 높이 ai( 1 <= ai <= 400000) 을 넘지는 못한다.

입력

출력

입출력 예

입력

3 -- 블록 수 
7 40 3 -- 높이 , 최대 높이 , 개수 
5 23 8
2 52 6

출력

48

힌트

아래 부터 2 번, 3 번 , 1 번을 4 개씩 놓을 경우는 규칙에 위배된다. 왜냐하면 1 번 블록은 40 을 넘을수는 없다.

블록 높이
---------
2    48
2    46
2    44
2    42
2    40
2    38
7    36
7    29
7    22
5    15
5    10
5     5 

출처: USACO 2005 March Gold