Adott (1 ≤ N ≤ 1000000) db, kezdetben üres doboz, ahol N páratlan egész. Egy lépésben néhány szomszédos dobozba beleteszünk egy-egy kavicsot. Adott (1 ≤ K ≤ 25000) db lépés, mindegyik lépés leírása két számot tartalmaz: x, y (x ≤ y). Ennek jelentése: az x. doboztól az y. dobozig minden dobozba teszünk még egy kavicsot. Ezek után az N doboz kavicsai számának mediánjára vagyunk kíváncsiak. Valahány páratlan szám mediánja a növekvő sorrendbe rendezett számsorból a középső elem.

A program olvassa be a standard input első sorából N-et és K-t, majd a következő K sorból az x, y számpárokat, és írja a standard output első és egyetlen sorába a medián értékét a végállapotban.