현금 인출기

어느 은행이 현금 인출기를 설치하려고 합니다. 요청된 금액에 대해 이 기계는 보유한 지폐로 금액을 지급합니다. 기계는 서로 다른 $N$가지 액면 $D_1, D_2, \dots, D_N$을 사용하며, 각 액면 $D_k$에 대해 $n_k$장의 지폐를 보유합니다.

예를 들어 $N = 3$이고 $(n_1, D_1) = (10, 100)$, $(n_2, D_2) = (4, 50)$, $(n_3, D_3) = (5, 10)$이면, 기계는 액면 100인 지폐 10장, 액면 50인 지폐 4장, 액면 10인 지폐 5장을 보유하고 있다는 뜻입니다.

요청 금액을 $\mathit{cash}$라 할 때, 보유한 지폐로 지급할 수 있는, $\mathit{cash}$를 넘지 않는 최대 금액을 계산하는 프로그램을 작성하세요.

입력은 여러 개의 데이터 집합으로 이루어지며, 파일의 끝(EOF)까지 읽습니다. 각 데이터 집합은 하나의 거래를 다음 형식으로 나타냅니다.

cash N n1 D1 n2 D2 ... nN DN

여기서 $0 \le \mathit{cash} \le 100000$은 요청 금액, $0 \le N \le 10$은 액면의 개수, $0 \le n_k \le 1000$은 액면 $D_k$의 보유 지폐 수이며, $k = 1, \dots, N$에 대해 $1 \le D_k \le 1000$입니다. 숫자 사이에는 공백이 자유롭게 들어갈 수 있습니다. 입력은 항상 올바른 형식입니다.

각 데이터 집합에 대해, 요청 금액을 넘지 않으면서 기계가 지급할 수 있는 최대 금액을 한 줄에 하나씩 출력하세요.

요청한 금액을 정확히 만들 수 없으면, 그 금액을 넘지 않는 범위에서 지급 가능한 최대 금액을 지급합니다. 기계에 지급할 지폐가 없거나(예: $N = 0$) 요청 금액이 $0$이면 지급 금액은 $0$입니다. 같은 지급 금액을 만드는 지폐 조합은 여러 가지일 수 있습니다.