E. Найрал хөгжим

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Паул найрал хөгжмийн тоглолтон дээр байна. Чавхдаст хөгжмийн хэсэг нь $r × c$ тэгш өнцөгт хэлбэртэй бөгөөд $n$ ширхэг хийлчид болон үлдсэн нь морин хийлчидээр дүүрчээ. Паул хийлэнд үнэхээр их дуртай, тиймээс тэрээр дор хаяж $k$ хийлчид оруулан зураг дарахыг хүсжээ. Паул нь тэнхлэгүүдтэй параллел тэгш өнцөгт ямар ч зургийг авч чадна. Паулын авч чадах хэдэн төрлийн ялгаатай зураг байгааг олно уу.

Хэрвээ 2 зургийн тэгш өнцөгтийн координатууд өөр бол энэ 2 зургийг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд 4-н зайгаар тусгаарлагдсан тоонууд $r$, $c$, $n$, $k$ ($1 ≤ r, c, n ≤ 3000$, $1 ≤ k ≤ min(n, 10)$) өгөгдөнө. Эдгээр нь өгөгдсөн дарааллаараа мөрийн тоо, баганын тоо, нийт хийлний тоо, Паулын зургыг нь авмаар байгаа хамгийн бага хийлний тоо.

Дараагийн $n$ ширхэг мөрөнд $i$ дэхь хийлний байрлал болох 2 бүхэл тоонууд $x_{i}$, $y_{i}$ ($1 ≤ x_{i} ≤ r$, $1 ≤ y_{i} ≤ c$) өгөгдөнө. Оролтонд нэг байрлал дахиж гарч ирэхгүй гэдэг нь баталгаатай.

Гаралт

Паул дор хаяж $k$ ширхэг хийл зурагт орохоор хэдэн ялгаатай зураг авч болохыг олж нэг бүхэл тоогоор хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
2 2 1 1
1 2
Гаралт
4
Оролт
3 2 3 3
1 1
3 1
2 2
Гаралт
1
Оролт
3 2 3 2
1 1
3 1
2 2
Гаралт
4

Тэмдэглэл

Бид морин хийлчнийг '$*$', хийлчнийг '$#$'-ээр тэмдэглэв.

Эхний жишээнд найрал хөгжим дараах байдлаар байрлаж байна:

*#  
**

Паул 4-н зураг авч чадна. Эдгээрт зөвхөн хийлчний байгаа байрлал, багана $1 × 2$, мөр $2 × 1$, болон бүхэл чавхдасын хэсгийг авах зэрэг орно.

2 дахь жишээнд найрал хөгжим дараах байдлаар байрлаж байна:

#*  
*#  
#*

Паул бүхэл хэсгийг бүхэлд нь зургийг нь авах шаардлагатай.

3 дахь жишээнд найрал хөгжим 2 дахь жишээтэй адилхан байрлаж байна.

Сэтгэгдлүүдийг ачааллаж байна...