โจทย์ปัญหา

ย่านการค้า JOI มีบริการบัตรสะสมแต้ม ในบัตรสะสมแต้มแต่ละใบจะมีช่องอยู่ $2N$ ช่อง เมื่อซื้อสินค้าจะสามารถจับสลากได้ และตามผลลัพธ์ที่ได้จะมีการประทับตรา "ถูกรางวัล" หรือ "ไม่ถูกรางวัล" ลงในช่อง โดยจะไม่มีการประทับตราลงในช่องเดิมซ้ำ $2$ ครั้ง บัตรสะสมแต้มที่มีตราถูกรางวัลตั้งแต่ $N$ ช่องขึ้นไปจากทั้งหมด $2N$ ช่องสามารถนำไปแลกของรางวัลได้ นอกจากนี้ ตราประทับบนบัตรสะสมแต้มยังสามารถขอให้แก้ไขใหม่ได้ในราคา $1$ เยนต่อ $1$ ช่อง

JOI-kun มีบัตรสะสมแต้มที่ช่องทั้ง $2N$ ช่องถูกประทับตราเต็มหมดแล้วอยู่ $M$ ใบ ในบัตรสะสมแต้มใบที่ $i$ ($1 \le i \le M$) มีตราถูกรางวัลอยู่ $A_i$ อัน และตราไม่ถูกรางวัลอยู่ $B_i$ อัน JOI-kun ต้องการของรางวัลอย่างน้อย $M - 1$ ชิ้น

จงหาค่าใช้จ่ายที่น้อยที่สุดที่จำเป็นเพื่อให้ JOI-kun ได้รับของรางวัลอย่างน้อย $M - 1$ ชิ้น

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วย $M + 1$ บรรทัด

ในบรรทัดที่ $1$ มีจำนวนเต็ม $2$ จำนวนคือ $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) เขียนคั่นด้วยช่องว่าง ซึ่งแสดงว่าบัตรสะสมแต้มมี $2N$ ช่อง และ JOI-kun มีบัตรสะสมแต้มอยู่ $M$ ใบ

ในบรรทัดที่ $i$ ($1 \le i \le M$) จาก $M$ บรรทัดถัดมา แต่ละบรรทัดมีจำนวนเต็ม $2$ จำนวนคือ $A_i, B_i$ ($0 \le A_i \le 2N$, $0 \le B_i \le 2N$, $A_i + B_i = 2N$) ซึ่งแสดงว่าบัตรสะสมแต้มใบที่ $i$ มีตราถูกรางวัลถูกประทับอยู่ $A_i$ อัน และตราไม่ถูกรางวัลถูกประทับอยู่ $B_i$ อัน

ข้อมูลส่งออก

จงแสดงค่าใช้จ่ายที่น้อยที่สุดที่จำเป็นเพื่อให้ JOI-kun ได้รับของรางวัลอย่างน้อย $M - 1$ ชิ้น ใน $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$ เยน จะทำให้มีบัตร $4$ ($= 5 - 1$) ใบที่สามารถนำไปแลกของรางวัลได้ และนี่คือค่าใช้จ่ายที่น้อยที่สุด

ในตัวอย่างข้อมูลนำเข้าที่ 2 เนื่องจากมีบัตร $3$ ($= 4 - 1$) ใบที่สามารถแลกของรางวัลได้อยู่แล้ว จึงไม่จำเป็นต้องแก้ไขตราประทับใดๆ