오래된 와인을 새 병에 담기

와인 병은 절대 가득 채우지 않는다. 온도 변화에 따른 팽창과 수축을 위해 병목에 약간의 공기를 남겨 두어야 하기 때문이다. 공기를 너무 적게 남기면 와인이 팽창하면서 코르크를 밀어낼 수 있고, 너무 많이 남기면 와인이 상할 수 있다. 따라서 각 병에는 최소 용량과 최대 용량이 정해져 있다.

주어진 양의 와인과 여러 크기의 병들이 있다. 사용하는 각 병을 그 병의 최소 용량과 최대 용량 사이로 채우면서, 담는 와인의 총량을 최대로 하고 싶다. 어떤 크기의 병을 몇 개 사용할지 정하라.

첫째 줄에 두 정수가 주어진다. 담아야 할 와인의 양(리터 단위, 0 이상 1,000,000 이하)과 병 크기의 종류 수(1 이상 100 이하)이다.

이어서 병 크기마다 한 줄씩, 그 크기의 최소 용량과 최대 용량이 밀리리터 단위로 주어진다. 최대 용량은 325 이상 4,500 이하이다. 최소 용량은 최대 용량의 95% 이상 99% 이하이다. 각 크기의 병은 원하는 만큼 얼마든지 사용할 수 있다.

와인의 양은 리터로, 병의 용량과 정답은 밀리리터로 주어진다(1리터 = 1,000밀리리터).

담을 수 없는 와인의 양을 밀리리터 단위 정수 하나로 출력한다.