E. Бомбочки
Задача BOMBS Задано поле m*n клітинок. В деяких з клітинок поля знаходяться міни. При вибуху міна спричиняє вибух усіх мін що знаходяться з нею в одному рядку чи стовчику ( вони в свою чергу теж спричиняють детоацію мін в їхніх рядках/стопвцях і т.д.). Ви можете покласти у незайняті клітинки поля не більше ніж s мін (не більше 1 міни в одну клітинку). Після цього ви можете підірвати одну із мін(не обов’язково з тих, що ви поклали). Ваша мета - досягти вибуху максимально можливої кількості мін.
Вхідні дані
Перший рядок місить 4 цілих числа - n, m, f, s - висота та ширина поля, початкова кількість мін та максимально можлива кількість доданих мін. 1 ≤ m, n ≤ 1000, 0 ≤ f, s ≤ m * n . Наступні f рядків містить по 2 цілих числа x та y (1≤x≤n , 1≤y≤m) – координати мін, що лежали на полі спочатку.
Вихідні дані
Єдиний рядок містить ціле число - максимально можлива для підриву кількість мін,.
Приклади
Вхідні дані
2 2 2 1
1 2
2 1
Вихідні дані
3
Вхідні дані
3 3 6 1
1 1
1 2
1 3
3 1
3 2
3 3
Вихідні дані
7
Вхідні дані
3 3 4 4
1 1
1 3
3 1
3 3
Вихідні дані
8