Taxtada sikkələr
Sizdə 'N' x 'M' ölçüsündə bir şahmat taxtası var. Taxtanın sətirləri '1'-dən 'N'-ə, sütunları isə '1'-dən 'M'-ə qədər nömrələnmişdir. Taxtanın bəzi xanalarında sikkələr var. Bir hərəkətlə siz taxtanın iki boş xanalarını (r[1], c[1]) və (r[2], c[2]) seçə bilərsiniz ki, r[1]-r[2] = DR, c[1]-c[2] = DC və hər birinə bir sikkə yerləşdirə bilərsiniz. Bu hərəkəti istədiyiniz qədər təkrarlaya bilərsiniz.
Sizdən taxtaya (artıq taxtada olanları nəzərə almadan) yerləşdirə biləcəyiniz maksimum sikkə sayını tapmaq tələb olunur.
Giriş məlumatları
Birinci sətirdə beş tam ədəd N, M, K, DR və DC boşluqla ayrılmış şəkildə verilir. Burada K - taxtanın əvvəlcədən sikkə olan xanalarının sayıdır. Növbəti K sətirin hər biri iki tam ədəd r[i] və c[i] boşluqla ayrılmış şəkildə ehtiva edir (müvafiq olaraq i-ci xananın sətir və sütun nömrəsi).
Çıxış məlumatları
Maksimum sikkə sayı.
Məhdudiyyətlər
1 ≤ N, M ≤ 1000000000 (10^9),1 ≤ DR, DC ≤ 1000000000 (10^9),0 ≤ K ≤ 100000 (10^5),1 ≤ r[j] ≤ N,1 ≤ c[j] ≤ M,bütün xanalardakı (r[j], c[j]) cütlər fərqlidir.
Qeydlər
Birinci nümunədə sizdə 3 x 3 ölçüsündə boş bir taxta var və DR = DC = 1. İlk hərəkətdə siz (1, 1) və (2, 2) cütünü seçə bilərsiniz,
ikinci hərəkətdə — (1, 2) və (2, 3),
üçüncü hərəkətdə isə — (2, 1) və (3, 2).