Freelancer Bidding (Minimum Customer Cost)

Choose one quote for each project and find the minimum total price to complete all projects; if any project has no quote, return −1. Quotes do not constrain one another.

输入格式

The first line contains the number of projects p and the number of quotes n, followed by n lines, each with a project ID and a quote. The original full bounds are 1≤p,n<500000, and project IDs are 0..p−1 as in the original example. The original range of quote values is missing; this site adds −10^9..10^9. Output the exact integer.

输出格式

Output a single integer answer.

样例 1

输入：

3 4
2 8
0 7
1 6
2 9

输出：

21

样例 2

输入：

4 3
2 8
0 7
1 6

输出：

-1

样例 3

输入：

1 2
0 0
0 -2

输出：

-2

样例说明

The outputs of the three public examples are, in order: 21; -1; -2. Verified by independent enumeration or direct simulation.