Đề bài

Khu phố mua sắm JOI có cung cấp dịch vụ thẻ tích điểm. Mỗi thẻ tích điểm có $2N$ ô. Khi mua hàng, khách có thể rút thăm, và tùy theo kết quả mà con dấu "trúng" hoặc "trượt" sẽ được đóng vào một ô. Không có ô nào bị đóng dấu $2$ lần. Một thẻ tích điểm có từ $N$ ô trở lên được đóng dấu trúng trong tổng số $2N$ ô có thể đem đổi lấy một phần thưởng. Ngoài ra, con dấu trên thẻ tích điểm có thể được sửa lại với giá $1$ yên cho mỗi $1$ ô.

JOI-kun đang có $M$ thẻ tích điểm mà cả $2N$ ô đều đã được đóng dấu kín. Trên thẻ tích điểm thứ $i$ ($1 \le i \le M$), có $A_i$ dấu trúng và $B_i$ dấu trượt. JOI-kun muốn có ít nhất $M - 1$ phần thưởng.

Hãy tìm chi phí tối thiểu cần thiết để JOI-kun nhận được ít nhất $M - 1$ phần thưởng.

Dữ liệu vào

Dữ liệu vào gồm $M + 1$ dòng.

Ở dòng $1$, có $2$ số nguyên $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) được ghi cách nhau bởi khoảng trắng. Điều này cho biết mỗi thẻ tích điểm có $2N$ ô và JOI-kun có $M$ thẻ tích điểm.

Ở dòng thứ $i$ ($1 \le i \le M$) trong $M$ dòng tiếp theo, mỗi dòng ghi $2$ số nguyên $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$), cho biết thẻ tích điểm $i$ có $A_i$ dấu trúng và $B_i$ dấu trượt.

Kết quả

In ra trên $1$ dòng chi phí tối thiểu cần thiết để JOI-kun nhận được ít nhất $M - 1$ phần thưởng.

Ví dụ

Ví dụ 1 - Dữ liệu vào

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

Ví dụ 1 - Kết quả

4

Ví dụ 2 - Dữ liệu vào

5 4
5 5
8 2
3 7
8 2

Ví dụ 2 - Kết quả

0

Trong Ví dụ 1, nếu JOI-kun sửa $3$ dấu trượt trên thẻ tích điểm $1$ thành dấu trúng và sửa $1$ dấu trượt trên thẻ tích điểm $3$ thành dấu trúng, thì với $4$ yên, $4$ ($= 5 - 1$) thẻ có thể đổi được phần thưởng, và đây là chi phí tối thiểu.

Trong Ví dụ 2, vì đã có sẵn $3$ ($= 4 - 1$) thẻ có thể đổi được phần thưởng nên không cần phải sửa lại bất kỳ con dấu nào.