4555 - 장보기

Time Limit: 1s Memory Limit: 128MB

Submissions: 159 Solved: 75
Description

장을 보려고 한다. 1~n 상품을 전부 사려면 최소 얼마의 금액이 필요한지 계산해보자.

Input

*Line 1: 필요한 상품 갯수 n (1≤n≤1000)

*Line 2: 입력의 갯수 N (n≤N≤100000)

*Line 3~N+2: 상품번호 i, 가격 p (이 때, 1~n 중 입력되지 않는 상품은 없다.)  (-1000≤i≤10000, 0≤p≤100000)

Output

Line 1: 상품 1~n을 전부 구매하기 위한 금액의 최솟값

Sample Input
3
10
1 10000
2 15000
3 10000
4 15000
5 10000
5 20000
4 10000
3 2000
2 100000
1 40000
Sample Output
27000