Lan truyền

Trong một khu phố, mỗi nhà hàng xóm đều bắt chước màu sơn xám của các ngôi nhà. Vì vậy, vào ngày một số ngôi nhà được sơn màu xám, mỗi nhà nằm liền kề theo chiều ngang hoặc chiều dọc với những ngôi nhà đó sẽ quyết định sơn nhà mình theo cách tương tự. Việc đó mất một tháng. Sau đó, những ngôi nhà nằm liền kề theo chiều ngang hoặc chiều dọc với các ngôi nhà ấy cũng quyết định làm như vậy, và họ cũng mất một tháng, cứ thế tiếp diễn.

####X        ##XXX       #XXXX        XXXXX
##X##        #XXXX       XXXXX       XXXXX
#####         ##X##       #XXXX        XXXXX
 Tháng 1            Tháng 2           Tháng 3           Tháng 4

Như bạn thấy, lúc đầu chỉ có hai ngôi nhà được sơn màu xám ([1,5] và [2,3]). Sau một tháng, có 8 ngôi nhà được sơn màu xám, đó là những ngôi nhà ở phía trên, phía dưới, bên phải và bên trái của các ngôi nhà đã được sơn. Sau hai tháng, có 13 ngôi nhà được sơn màu xám, và sau 3 tháng, mọi ngôi nhà trong khu phố đều được sơn màu xám.

Đầu vào cho bạn hai số tự nhiên H và W, lần lượt biểu thị chiều cao và chiều rộng của khu phố. Ở dòng tiếp theo, bạn được cho số tự nhiên N, biểu thị số ngôi nhà cần được sơn màu xám. Ở dòng tiếp theo, bạn được cho số tự nhiên M. Trong M dòng tiếp theo, bạn được cho hai số tự nhiên X và Y, biểu thị vị trí của những ngôi nhà đã được sơn màu xám.

Xuất ra số tháng cần để sơn màu xám tổng cộng N ngôi nhà, bao gồm cả những ngôi nhà ban đầu đã được sơn.

Đầu vào
3 5
7
2
1 5
2 3

Đầu ra
1

Giải thích #1: Đây là ví dụ đã nêu trong phần văn bản phía trên. Khu phố có chiều cao 3 và chiều rộng 5. Ta cần xuất ra số tháng cần thiết để sơn màu xám tổng cộng 7 ngôi nhà. Có 2 ngôi nhà đã được sơn màu xám, nằm ở vị trí [1, 5] và [2,3]. Vậy cần một tháng để sơn màu xám tổng cộng 7 ngôi nhà.