Színház
Egy színházi előadást olyan teremben tartanak,
ahol $M$ db ülőhely van.
Az ülőhelyek 1-től $M$-ig sorszámozottak.
A szervezők megrendeléseket fogadnak. Minden megrendelés egy
$A, B$ számpárt tartalmaz, ami azt jelenti, hogy a megrendelő olyan ülőhelyet szeretne kapni, amelynek $S$ sorszáma $A$ és $B$ közé esik $(A\le S\le B)$.
Feladat
Készíts programot, amely kiszámítja, hogy a szervezők a megrendelések alapján a legjobb esetben hány megrendelést tudnak kielégíteni és meg is ad egy olyan jegykiosztást, amely kielégíti a megrendeléseket!
Bemenet
Az input (szinhaz.be)
állomány első sorában két egész szám van, $M$ és $N$.
$M$ az ülőhelyek száma $(1\le M\le 1000)$,
$N$ $(1\le N\le 1000)$ pedig a megrendelések száma.
A következő $N$ sor mindegyike két egész számot
$A, B$ $(1\le A\le B\le M)$ tartalmaz egy szóközzel elválasztva. Az állomány $i+1$-edik sorában lévő megrendelés sorszáma $i$.
Kimenet
A kimenet (szinhaz.ki)
első sorába a legtöbb kielégíthető megrendelés $K$ számát kell írni! A további $K$ sor tartalmazza a jegykiosztást, minden sor két egész számot tartalmazzon egy szóközzel elválasztva. Az első szám egy megrendelés sorszáma, a második pedig azon ülőhely sorszáma, amelyet a megrendelő kap. A kiosztás kiírása tetszőleges sorrendben lehet. Ha több megoldás van, akkor egy tetszőlegeset ki lehet írni.
Példa
| szinhaz.be | szinhaz.ki |
| 10 6 3 3 2 2 2 3 1 3 1 2 2 4 | 4 5 1 2 2 1 3 6 4 |