JOI 상점가에서는 포인트 카드 서비스를 실시하고 있다. 각 포인트 카드에는 도장을 찍을 수 있는 칸이 총 2N개 있어, 상품을 구매하면 뽑기를 해서 결과에 따라 '당첨' 또는 '꽝' 도장이 찍힌다. 한 칸에 두 번 이상 도장을 찍을 수는 없다. 2N개 중 N개 이상의 칸에 당첨 도장이 찍힌 포인트 카드는 경품과 교환할 수 있다. 또, 한 칸에 찍힌 도장을 1엔을 내고 다른 도장으로 바꿀 수 있다.

JOI 군은 2N개 칸을 다 채운 포인트 카드를 M장 가지고 있다. i번째 포인트 카드에는 A_i개의 당첨 도장과, B_i개의 꽝 도장이 찍혀 있다.

JOI 군은 M-1개 이상의 경품을 가지려고 한다. 이에 필요한 비용의 최솟값을 구하라.

입력 형식

입력은 M+1줄로 이루어진다.

첫 줄에는 2개의 정수 N, M(1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000)이 공백을 사이에 두고 주어진다. 이는 포인트 카드에 2N개의 칸이 있고, JOI 군이 M장의 포인트 카드를 가지고 있음을 나타낸다.

다음 M개 줄 중 i번째(1 ≤ i ≤ M) 줄에는 각각 2개의 정수 A_i, B_i (0 ≤ A_i ≤ 2N, 0 ≤ B_i ≤ 2N, A_i + B_i = 2N)가 주어지며, 포인트 카드 i에 A_i개의 당첨 도장과 B_i개의 꽝 도장이 찍혀 있음을 나타낸다.

출력 형식

JOI 군이 M-1개 이상의 경품을 얻기 위해 필요한 비용의 최솟값을 엔 단위로 한 줄로 출력하라.

예제 입력 1

4 5
1 7
6 2
3 5
4 4
0 8

예제 출력 1

4

예제 입력 2

5 4
5 5
8 2
3 7
8 2

예제 출력 2

0

힌트

예제 입출력 1에서, 포인트 카드 1의 꽝 도장 3개와 포인트 카드 3의 꽝 도장 1개를 당첨 도장으로 바꾸면, 4엔으로 5-1=4장의 카드가 경품과 교환 가능하게 되어, 이것이 최소 비용이다.

예제 입출력 2에서, 이미 4-1=3장의 카드가 경품과 교환 가능하므로 도장을 바꿀 필요가 없다.