2969-й год. Прошло 1000 лет с момента посадки на луну. Человечество колонизировало Гиперпространство и жило в гармонии.
Жило, пока мы не поняли, что мы не одни.
Не очень далеко от Земли многочисленный космический флот инопланетян готовит атаку на Землю. Впервые за долгое время человечеству угрожает реальная опасность. Повсюду паника и кризис. Ученые со всей солнечной системы встретились и обсуждают возможный выход из ситуации. Но пока все усилия тщетны.
Последняя надежда Земли — ВЫ!
К счастью, Земля имеет мощную систему защиты, созданную специалистами из MDCS. Флот инопланетян содержит $$$N$$$ кораблей на одной линии. Система защиты состоит из трех типов вооружения:
Ваша задача — найти такой план атаки на корабли инопланетян, чтобы уничтожить максимально возможное количество кораблей. Каждый уничтоженный корабль должен быть уничтожен ровно одним оружием.
Первая строка содержит два целых числа — количество оружия $$$N$$$ $$$(1\leq N\leq 5000)$$$ и количество кораблей $$$M$$$ $$$(1\leq M\leq 5000)$$$.
Каждая из следующих $$$N$$$ строк начинается с одного целого числа, которое обозначает тип оружия (0, 1 или 2). Если тип равен 0, то это оружие — SQL-ракета, и далее эта строка содержит строго положительное число $$$K$$$ $$$(\sum{K} \leq 100 000)$$$ и массив $$$k_i$$$ $$$(1\leq k_i\leq M)$$$ из $$$K$$$ целых чисел. Если тип равен 1, то это луч Познания, а строка далее содержит целые числа $$$l$$$ и $$$r$$$ $$$(1\leq l\leq r\leq M)$$$. Если тип равен 2, то это OMG-базука, а строка далее содержит различные числа $$$a$$$, $$$b$$$ и $$$c$$$ $$$ (1 \leq a,b,c \leq M)$$$.
Первая строка должна содержать максимальное количество уничтоженных кораблей $$$X$$$.
Каждая из следующих $$$X$$$ строк должна содержать два целых числа $$$A$$$ и $$$B$$$, где $$$A$$$ — номер оружия, а $$$B$$$ — номер корабля, уничтоженного оружием $$$A$$$.
3 5
0 1 4
2 5 4 1
1 1 4
4
2 1
3 2
1 4
2 5
SQL-ракета может уничтожить только четвертый корабль. OMG-базука может уничтожить два из 1-го, 4-го или 5-го кораблей, а луч Познания может уничтожить любой корабль из отрезка $$$[1,4]$$$. Максимальное количество уничтоженных кораблей равно 4, один из возможных планов — SQL-ракета уничтожает 4-й корабль, OMG-базука уничтожает 1-й и 5-й корабли, а луч Познания уничтожает 2-й корабль.
Название |
---|