المسألة

يقدم شارع التسوق JOI خدمة بطاقات النقاط. تحتوي كل بطاقة نقاط على $2N$ مربعاً. عند شراء سلعة، يمكن سحب قرعة، وبناءً على النتيجة يُختم على أحد المربعات بختم «فوز» أو «خسارة». لا يُختم على المربع الواحد $2$ مرتين. يمكن استبدال بطاقة النقاط التي تحتوي على أختام فوز في $N$ مربعات أو أكثر من أصل $2N$ مربعاً بجائزة. كما يمكن تعديل الختم في بطاقة النقاط مقابل $1$ ين لكل $1$ مربع.

يمتلك JOI-kun عدد $M$ من بطاقات النقاط التي امتلأت جميع مربعاتها البالغ عددها $2N$. في بطاقة النقاط $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$ ختم خسارة.

الإخراج

اطبع في سطر $1$ أقل تكلفة لازمة لكي يحصل JOI-kun على $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، إذا تم تعديل $3$ أختام خسارة في بطاقة النقاط $1$ إلى أختام فوز، وتعديل $1$ ختم خسارة في بطاقة النقاط $3$ إلى ختم فوز، فإنه مقابل $4$ ينات تصبح $4$ ($= 5 - 1$) بطاقات قابلة للاستبدال بجوائز، وهذه هي التكلفة الدنيا.

في مثال الإدخال 2، بما أن هناك $3$ ($= 4 - 1$) بطاقات قابلة للاستبدال بجوائز بالفعل، فلا داعي لتعديل أي ختم.