F. Найрал Хөгжим

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

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

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

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

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

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

Оролт

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

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

Гаралт

Дор хаяж $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

Тэмдэглэл

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

Эхний жишээнд чуулган дараах байдлаар харагдана:

*#  
**

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

2-дахь жишээнд чуулган дараах байдлаар харагдана:

#*  
*#  
#*

Энэ тохиолдолд Паул заавал бүтэн чуулганы зургийг дарах ёстой юм.

3-дахь жишээнд, чуулган 2-дахь жишээтэй ижилхэн харагдана.

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