На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.
Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:
- Ящик под номером i поступает на склад.
- Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
- Поступающий ящик помещается наверх найденной или сформированной стопки.
- Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.
Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.
Ваша задача написать программу, которая сможет оценить эффективность данной системы и посчитает сколько ящиков будут отправлены после окончания обработки поступающих ящиков.
Входные данные
В первой находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа xi и yi (1 ≤ xi ≤ m; 1 ≤ yi ≤ k) — номер размера и номер цвета ящика, который поступит i-м на склад.
Выходные данные
Требуется вывести одно число — сколько ящиков будут отправлены.
Пример входных и выходных данных
Вывод |
Ввод |
5 2 1
1 1
2 1
1 1
2 1
1 1 |
4 |
5 1 2
1 1
1 2
1 1
1 2
1 1 |
0 |