PIIMA

Xotira 32 MB Vaqt 1000 ms

14

Bomba

Shohruh yaqinda R radiusli bomba ixtiro qildi. Katakcha bomba radiusida joylashgan deb ataladi, qachonki gorizontal va vertikal masofalar farqining minimali R dan oshmasa. Boshqacha aytganda, agar bomba (a, b) koordinatada, katakcha (c, d) koordinatada joylashgan va \(min(|a-c|, |b-d|) \le R\) bo'lsa, shu katakcha bomba radiusida joylashgan bo'ladi.

\(N*M\) maydon berilgan, har bir katakcha kamida bomba radiusida joylashishi uchun minimal nechta bomba kerak bo'ladi?

Kiruvchi ma'lumotlar:

Kirish faylining yagona qatorida 3 ta butun son - N, M\((1 \le N, M \le 1000)\) va R\((0 \le R \le 1000)\) kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida kerak bo'ladigan minimal bombalar sonini chop eting.

Misollar

#	input.txt	output.txt
1	1 7 3	1
2	5 5 0	5

Izoh:

1-test uchun koordinatalar:

(1,2)

2-test uchun koordinatalar:

(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 5)

(Aynan shu koordinatalar bo'lishi shart emas, muhimi minimal bo'lishi lozim).

Masala #1180

Bomba