Khu phố mua sắm JOI có một chương trình thẻ tích điểm. Mỗi thẻ có \(2N\) ô. Khi mua hàng, khách hàng được rút thăm; tùy theo kết quả, một dấu "trúng" hoặc "trượt" được đóng vào một ô. Không ô nào bị đóng dấu hai lần. Một thẻ có dấu "trúng" trong ít nhất \(N\) trên tổng số \(2N\) ô có thể được đổi lấy một phần quà.

Ngoài ra, có thể đổi dấu trong một ô với chi phí \(1\) yên.

JOI có \(M\) thẻ tích điểm mà cả \(2N\) ô đều đã được đóng dấu. Thẻ thứ \(i\) (\(1 \le i \le M\)) có \(A_i\) dấu "trúng" và \(B_i\) dấu "trượt". JOI muốn nhận được ít nhất \(M-1\) phần quà.

Hãy tính chi phí nhỏ nhất để JOI nhận được ít nhất \(M-1\) phần quà.

Dữ liệu vào

Dữ liệu vào gồm \(M+1\) dòng:

• Dòng thứ nhất chứa hai số nguyên \(N, M\); mỗi thẻ có \(2N\) ô và JOI có \(M\) thẻ.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i, B_i\), mô tả số dấu "trúng" và số dấu "trượt" trên thẻ thứ \(i\).

Dữ liệu ra

In ra một số nguyên trên một dòng: chi phí nhỏ nhất để JOI nhận được ít nhất \(M-1\) phần quà.

Ràng buộc

Các giá trị thỏa mãn:

• \(1 \le N \le 1\,000\).
• \(1 \le M \le 1\,000\).
• \(0 \le A_i \le 2N\).
• \(0 \le B_i \le 2N\).
• \(A_i+B_i=2N\).

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

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

4

5 4
5 5
8 2
3 7
8 2

0

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 2: Point Card.