Есептің шарты

JOI сауда көшесінде ұпай карталары қызметі жұмыс істейді. Әрбір ұпай картасында $2N$ торкөз бар. Тауар сатып алған кезде жеребе тартуға болады, және оның нәтижесіне қарай торкөзге «ұтыс» немесе «ұтылыс» мөрі басылады. Бір торкөзге мөр $2$ рет басылмайды. $2N$ торкөздің кемінде $N$ торкөзіне ұтыс мөрі басылған ұпай картасын жүлдеге айырбастауға болады. Сонымен қатар, ұпай картасындағы мөрді әр $1$ торкөз үшін $1$ иена төлеп өзгертіп жаздыруға болады.

JOI-кунда барлық $2N$ торкөзі толтырылған $M$ ұпай картасы бар. $i$-ші ұпай картасында ($1 \le i \le M$) $A_i$ ұтыс мөрі және $B_i$ ұтылыс мөрі басылған. JOI-кун кемінде $M - 1$ жүлде алғысы келеді.

JOI-кун кемінде $M - 1$ жүлде алуы үшін қажетті ең аз шығынды табыңыз.

Кіріс деректер

Кіріс деректер $M + 1$ жолдан тұрады.

$1$-ші жолда бос орын арқылы бөлінген $2$ бүтін сан $N, M$ ($1 \le N \le 1000$, $1 \le M \le 1000$) жазылған. Бұл ұпай картасында $2N$ торкөз бар екенін және JOI-кунда $M$ ұпай картасы бар екенін білдіреді.

Келесі $M$ жолдың $i$-ші жолында ($1 \le i \le 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-кун кемінде $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$) картаны қазірдің өзінде жүлдеге айырбастауға болатындықтан, ештеңені өзгертудің қажеті жоқ.