도둑이 보석상에 침입하여 보석을 훔쳐가려고 한다. 그런데 도둑이 가져 갈수 있는 보석의 무게(n)은 한정되어 있다.

각각의 보석의 무게(weight)와 값(value)을 가지고 있다. 무게 n 으로 어떤 보석을 가져 가는게 가장 많은 이윤(?)을 취할 수 있는 가를 구하는게 문제이다.

단, 보석은 쪼갤 수 있고 종류당 하나씩 있다고 하자.

입력 방법

출력 방법

출력은 소수 3 번째 자리에서 반올림하여 2 자리까지 출력한다.

입출력 예

입력

30
3
5 50
10 60
20 140

출력

220.00