Школьник Миша устал заниматься спортивным программированием, и поэтому решил все бросить и уйти в магический лес торговать магическими яблоками.
Его друг Даня пришел в этот магический лес, чтобы навестить Мишу. Какого же было его удивление, когда он узнал, что Миша нашел там много друзей, таких же бывших спортивных программистов. И у всех них, как и у Миши, есть своя лавка, где они продают магические яблоки. Чтобы поддержать друзей, так кардинально поменявших свою жизнь, он решил скупить у них весь ассортимент.
Процесс покупки устроен следующим образом: всего есть \(n\) лавок, пронумерованных целыми числами от \(1\) до \(n\), и \(m\) видов магических яблок, пронумерованных целыми числами от \(1\) до \(m\). В каждой лавке продается какое-то множество видов яблок. Даня посещает все лавки в порядке возрастания номера, начиная с первой. Заходя в лавку он покупает по одному магическому яблоку каждого вида, который в этой лавке продается, и кладет их к себе в рюкзак.
Однако, магические яблоки не были бы магическими, если бы с ними было все в порядке. Дело в том, что когда два яблока одного типа оказываются вместе в рюкзаке, все яблоки в нем магическим образом исчезают. Важно, что исчезновение происходит уже после того, как Даня положил яблоки в рюкзак и покинул лавку.
Вернувшись домой, Даня понял, что где-то в лесу он успел потерять свой рюкзак. Помня для некоторых лавок, какие виды магических яблок в них продавались, он хочет узнать, какое максимальное количество яблок могло оказаться у него в рюкзаке после всех покупок в лучшем случае.
Выходные данные
Для каждого набора данных выведите одно целое число — максимальное количество яблок, которое могло оказаться в рюкзаке Дани после посещения всех лавок в лучшем случае.
Примечание
В первом наборе входных данных Даня помнит про все лавки, поэтому процесс будет детерминированным. В первой лавке он возьмет два яблока, и еще два во второй, но после того как он положит их в рюкзак, они исчезнут. Поэтому в конце останется только \(2\) яблока, которые он возьмет в третьей лавке.
Во втором наборе входных данных, если в третьей лавке будет пусто, то после посещения четвертой лавки все яблоки исчезнут. В любом другом случае яблоки исчезнут после третьей лавки, и в четвертой Даня сможет взять одно яблоко, поэтому ответ \(1\).
В третьем наборе входных данных, в первой лавке могут продаваться все виды яблок, а во второй лавке может ничего не продаваться. Тогда в конце останутся все \(5\) яблок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 4
2 1 2
2 4 1
2 1 2
4 4
2 1 2
2 3 4
0
1 1
2 5
0
0
5 3
0
3 1 2 3
2 3 1
0
1 3
|
2
1
5
3
|