포인트 카드

문제

JOI 상점가에서는 포인트 카드 서비스를 하고 있다. 각 포인트 카드에는 2N 개의 칸이 있다. 상품을 구입하면 제비를 뽑을 수 있고, 결과에 따라 "당첨" 또는 "꽝" 표시가 칸에 찍힌다. 같은 칸에 표시가 두 번 찍히는 일은 없다. 2N 개의 칸 중 N 개 이상의 칸에 당첨 표시가 적힌 포인트 카드는 경품과 교환할 수 있다. 또한, 포인트 카드의 표시는 한 칸당 1 원으로 고쳐 쓸 수 있다.

JOI 군은 2N 개의 칸이 모두 채워진 포인트 카드를 M 장 가지고 있다. 포인트 카드 i (1 ≦ i ≦ M) 에는 $A_{i}$ 개의 당첨 표시와 $B_{i}$ 개의 꽝 표시가 찍혀 있다. JOI 군은 M - 1 개 이상의 경품을 원한다.

JOI 군이 M - 1 개 이상의 경품을 얻기 위해 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

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

예제 1 에서는, 포인트 카드 1 의 꽝 표시 3 개를 당첨 표시로 고쳐 쓰고, 포인트 카드 3 의 꽝 표시 1 개를 당첨 표시로 고쳐 쓰면, 4 원으로 4 (= 5 - 1) 장의 카드를 경품과 교환할 수 있게 되며, 이것이 최소 비용이다.

예제 입력 2

5 4
5 5
8 2
3 7
8 2

예제 출력 2

0

예제 2 에서는, 이미 3 (= 4 - 1) 장의 카드를 경품과 교환할 수 있으므로, 고쳐 쓸 필요가 없다.