Еден стар монитор има димензија MxN пиксели т.е. има M редови со по N пиксели. Дел од пикселите од мониторот се расипани и тие прават пречки кои влијаат на целата слика на мониторот.

Има два типа на расипани пиксели. Првиот тип на расипани пиксели прави црна хоризонтална линија низ целата сликата на мониторот која минува низ расипаниот пиксел. Вториот тип на расипани пиксели прави црна вертикална линија низ целата слика на мониторот која минува низ расипаниот пиксел. Еден пиксел може да биде расипан и од прв и втор тип и тој прави и црна хоризонтална и црна вертикална линија која минува низ расипаниот пиксел и тогаш тој пиксел е расипан и од прв и од втор тип.

На мониторот отвораме слика со димензии KxK пиксели. Сакаме да ја поставиме така што сликата во целост ќе се наоѓа на мониторот (во целост значи дека сите пиксели од сликата би се гледале, ако мониторот е исправен). Колку најмалку црни линии (хоризонтални и вертикални) поминуваат низ сликата?

Влез

Во првиот ред се запишани два броја М и N кои го претставуваат бројот на пиксели по должина и ширина на мониторот (1<= N, М <= 10 000) .

Во вториот ред е запишан бројот K кој ја претставува димензијата на сликата која ја отвораме (1<= К <= 10 000, К<=N, К<=M) .

Во третиот ред е запишан бројот на расипани пиксели P (1<= P <= 50 000).

Во следните P реда се запишани по три броја: X[i], Y[i], T[i], i=1…P одделени со празно место. X[i] го означува редот во кој се наоѓа i-иот расипан пиксел. Y[i] ја означува колоната во која се наоѓа i-тиот расипан пиксел. P[i] го претставува типот на i-тиот расипан пиксел: 1 ако е од прв тип или 2 ако е од втор тип. (1<=X[i]<=M, 1<=Y[i]<=N)

Излез

Во првиот ред запишете еден број: колку најмалку црни линии може да поминат низ сликата.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
4 3
2
1
1 3 1

излез
0

влез
4 3
2
1
3 2 2

излез
1

влез
4 3
2
3
2 1 1
1 3 2
4 2 1

излез
1

Објаснување за првиот тест пример: Мониторот има 4 редици од пиксели и во секој ред има по 3 пиксели. Треба да се постави слика со димензија 2x2. Сликата може да се постави на 6 различни начини (во првите два реда и првите две колони, во првите два реда и втората и третата колона, во вториот и третиот ред и во првата и втората колона, во вториот и третиот ред и втората и третата колона, во третиот и четвртиот ред и во првата и втората колона, во третиот и четвртиот ред и втората и третата колона). Единствениот расипан пиксел прави црна хоризонтална линија во првата редица. Затоа со првите два начини на поставувања на сликата низ сликата ќе поминува една црна линија. Со сите останати случаи нема хоризонтална, а ни вертикална линија. Минималниот број на линии е 0.

Објаснување за вториот тест пример: Даден е монитор со 4 редици и 3 колони од пиксели. Поради единствениот расипан пиксел се јавува црна вертикална линија во втората колона. Сите можни начини на кои може да се прикаже сликата ќе содржат дел од втората колона па мора на сликата поминува црната линија. Затоа што станува збор за една линија резултатот е 1.

Објаснување за третиот тест пример: Ако сликата се гледа во првите две редици и првите колони на сликата ќе поминува една хоризонтална линија поради распаниот пиксел кој се наоѓа во 2-рата редица и 1-вата колона. Ако сликата се гледа во првите две редици и втората и третата колона на сликата ќе поминуваат 2 црни линии. Едната е хоризонтална поради пикселот во 2-рата редица и 1-вата колона. Другата е вертикална и се јавува поради расипаниот пиксел во 1-вата редица и 3-тата колона. Ако се разгледаат и сите други можни места на мониторот каде што ќе може да се види целата слика ќе се увиди дека нема место каде што низ сликата нема да поминуваат црни линии. Оттука минималниот број на црни линии кои ќе се гледаат на сликата е 1.