محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

یک زمین موزاییک کاری شده‌ی پهناور داریم و بچه‌های محل می‌خواهند در آن بازی کنند. مشکلی که وجود دارد این است که بعضی از این موزاییک‌ها شکسته شده و بچه‌ها می‌ترسند که پایشان گیر کند و آسیب ببینند. آن‌ها تصمیم گرفتند که یک زیر مستطیل به تعداد $S$ موزاییک‌، از این زمین را انتخاب کنند که در آن هیچ موزاییک خرابی وجود نداشته باشد. حال شما باید به آن‌ها بگویید برای این کار چند انتخاب دارند؟

ورودی

در خط اول ورودی، به ترتیب $X$ (اندازه‌ی طول زمین) و $Y$ (اندازه‌ی عرض زمین) با یک فاصله از هم وارد می‌شود.
در خط دوم ورودی، $S$ (تعداد موزاییک‌های زمین انتخابی) وارد می‌شود.
در خط سوم ورودی، $n$ (تعداد موزاییک های خراب) وارد می‌شود.
سپس در $n$ خط بعدی در هر خط دو عدد طول و عرض مختصات موزاییک‌های شکسته شده با یک فاصله از هم وارد می‌شوند. (مختصات تکراری وارد نمی‌شود.)

$$ 1 \le X, Y \le 250$$ $$ 0 \le n \le X * Y $$$$ 1 \le S \le X * Y $$$$ 1 \le x_i \le X $$$$ 1 \le y_i \le Y $$

خروجی

خروجی تنها شامل یک عدد است که تعداد زیر مستطیل‌های با تعداد $S$ موزاییک را نمایش می‌دهد.

مثال

ورودی نمونه ۱

خروجی نمونه ۱

توضیحات نمونه‌ی ۱

با توجه به تصویر و جدول زیر تعداد زمین‌های بازی مستطیل شکل با ۴ موزاییک، ۱۲ تاست. بنابراین عدد ۱۲ در خروجی چاپ می‌شود.

	موزاییک‌های تحت پوشش
زمین ۱	۱ ۲ ۸ ۹
زمین ۲	۳ ۴ ۱۱ ۱۲
زمین ۳	۴ ۵ ۱۲ ۱۳
زمین ۴	۵ ۶ ۱۳ ۱۴
زمین ۵	۶ ۷ ۱۴ ۱۵
زمین ۶	۳ ۴ ۵ ۶
زمین ۷	۴ ۵ ۶ ۷
زمین ۸	۸ ۹ ۱۰ ۱۱
زمین ۹	۹ ۱۰ ۱۱ ۱۲
زمین ۱۰	۱۰ ۱۱ ۱۲ ۱۳
زمین ۱۱	۱۱ ۱۲ ۱۳ ۱۴
زمین ۱۲	۱۲ ۱۳ ۱۴ ۱۵

ورودی نمونه ۲

خروجی نمونه ۲

توضیحات نمونه‌ی ۲

با توجه به تصویر و جدول زیر تعداد زمین‌های بازی مستطیل شکل با ۲ موزاییک، ۱۱ تاست. بنابراین عدد ۱۱ در خروجی چاپ می‌شود.

	موزاییک‌های تحت پوشش
زمین ۱	۱ ۲
زمین ۲	۲ ۳
زمین ۳	۲ ۸
زمین ۴	۷ ۱۱
زمین ۵	۱۱ ۱۲
زمین ۶	۹ ۱۴
زمین ۷	۱۳ ۱۴
زمین ۸	۱۴ ۱۵
زمین ۹	۴ ۵
زمین ۱۰	۵ ۶
زمین ۱۱	۵ ۱۰

ارسال پاسخ برای این سؤال