p01887 Pipe Fitter and the Fierce Dogs_28807
Example

Input

5 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4


Output

6
from collections import defaultdict
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    W, H, K = map(int, readline().split())
    N = int(readline())
    mp = defaultdict(lambda:defaultdict(int))
    for i in range(N):
        x, y = map(int, readline().split())
        if y % 2 == 1:
            continue
        if x % 2 == 1:
            mp[y][x//2] |= 1
            if x < W:
                mp[y][x//2+1] |= 4
        else:
            mp[y][x//2] |= 2
    if K < W//2:
        write("-1\n")
        return
    K -= W//2+1
    r = 0
    for y, mp_xs in mp.items():
        *S, = mp_xs.items()
        S.sort()
        a = 0; b = 10**9
        prv = -1
        for x, bs in S:
            if x - prv > 1:
                a = b = min(a, b)
            v0 = ((bs & 1) > 0); v1 = ((bs & 2) > 0); v2 = ((bs & 4) > 0)
            a, b = min(a + v0, b + min(v0+v2, 2*v1)), min(a, b + v2)
            prv = x
        if prv < W // 2:
            c = min(a, b)
        else:
            c = a
        r += c
    ans = max((W//2+1)*(H//2) + max(r - K, 0) - K, 0)
    write("%d\n" % ans)
solve()

5 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4 9 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4 9 5 5
6
3 2
4 2
5 2
1 4
3 4
5 4 9 5 10
6
3 1
4 2
5 2
1 4
3 4
7 4 9 5 6
6
3 2
4 4
6 1
2 5
3 4
5 4 9 7 5
6
3 2
7 4
6 1
2 7
3 4
5 4 9 5 9
6
3 2
4 2
5 2
1 4
3 4
5 5 11 5 6
0
10 1
3 0
10 4
0 0
5 4
0 5 9 5 12
2
3 2
4 4
6 1
2 1
3 4
4 4 9 5 7
5
3 2
4 4
5 2
2 5
3 4
5 4 5 9 4
6
3 2
4 4
10 1
2 5
3 6
5 7 6 5 12
2
3 2
4 4
6 1
2 1
3 2
4 4 9 5 5
6
3 2
4 2
5 2
1 4
3 4
7 4 9 5 5
6
3 1
4 2
5 2
1 4
3 4
7 4 9 5 4
6
3 2
4 4
5 2
1 4
3 4
5 4 9 5 5
6
3 2
4 2
5 2
1 4
3 4
5 5 9 5 5
6
3 2
4 2
9 2
1 4
3 4
7 4 9 5 4
6
3 2
4 4
5 2
1 5
3 4
5 4 9 5 4
6
3 2
4 4
5 2
2 5
3 4
5 4 9 5 4
6
3 2
4 4
5 1
2 5
3 4
5 4 9 5 4
6
3 2
4 4
6 1
2 5
3 4
5 4 9 5 4
6
3 2
4 4
6 1
2 7
3 4
5 4 9 7 4
6
3 2
4 4
6 1
2 7
3 4
5 4 9 7 4
6
3 2
7 4
6 1
2 7
3 4
5 4 9 7 4
6
3 2
7 4
6 1
2 7
6 4
5 4 9 7 4
6
3 1
7 4
6 1
2 7
6 4
5 4 9 7 4
6
3 1
7 4
6 1
2 7
6 2
5 4 9 7 4
6
3 1
7 4
6 1
0 7
6 2
5 4 9 7 4
6
2 1
7 4
6 1
0 7
6 2
5 4 9 6 4
6
2 1
7 4
6 1
0 7
6 2
5 4 9 6 4
6
4 1
7 4
6 1
0 7
6 2
5 4 9 5 4
6
3 2
6 2
5 2
1 4
3 4
5 4 9 5 4
6
3 2
4 4
5 2
1 4
3 4
5 1 9 5 5
6
3 2
4 2
5 2
1 4
3 4
5 1 9 10 4
6
3 2
4 4
5 2
1 5
3 4
5 4 9 5 4
6
3 2
4 4
5 1
2 5
3 6
5 4 16 7 4
6
3 2
7 4
6 1
2 7
6 4
5 4 9 7 4
6
3 1
3 4
6 1
2 7
6 2
5 4 9 7 4
6
2 1
7 4
6 1
0 7
6 2
2 4 9 6 4
6
2 1
7 4
6 1
0 7
6 2
4 4 9 6 4
6
4 1
7 4
6 1
0 7
6 2
5 7 9 5 4
6
3 2
6 2
5 2
1 4
3 4
9 4 9 5 4
6
3 2
4 4
2 2
1 4
3 4
5 1 9 5 4
6
3 2
4 4
5 1
2 5
5 6
5 4 9 5 6
2
3 2
4 4
6 1
2 5
3 4
5 4 9 7 5
6
6 2
7 4
6 1
2 7
3 4
5 4 16 7 4
6
3 2
7 4
1 1
2 7
6 4
5 4 12 7 4
6
3 1
3 4
6 1
2 7
6 2
5 4 9 7 4
6
2 1
7 2
6 1
0 7
6 2
2 4 9 6 4
6
2 1
7 4
12 1
0 7
6 2
4 4 9 6 4
6
4 1
7 4
6 1
0 7
6 2
8 7 9 7 4
6
3 2
6 2
5 2
1 4
3 4
9 4 9 10 4
6
3 2
4 4
2 2
1 4
3 4
5 1 9 5 4
6
3 2
4 4
2 1
2 5
5 6
5 4 9 5 6
2
3 2
4 4
6 1
2 1
3 4
5 4 16 7 4
6
3 2
7 4
0 1
2 7
6 4
5 4 12 7 4
6
3 1
3 4
9 1
2 7
6 2
5 4 9 6 4
6
4 1
7 7
6 1
0 7
6 2
8 7 9 7 4
6
3 2
6 2
5 2
1 4
1 4
9 4 9 10 4
6
3 2
4 4
2 3
1 4
3 4
5 1 9 5 4
6
3 2
4 4
1 1
2 5
5 6
5 4 9 5 6
2
3 2
4 4
9 1
2 1
3 4
5 4 16 7 4
6
3 2
7 4
0 1
2 5
6 4
5 4 12 3 4
6
3 1
3 4
9 1
2 7
6 2
5 4 9 4 4
6
4 1
7 7
6 1
0 7
6 2
8 7 9 10 4
6
3 2
4 5
2 3
1 4
3 4
5 1 9 5 4
2
3 2
4 4
9 1
2 1
3 4
5 4 12 3 4
6
3 1
3 4
9 1
2 7
6 2
5 2 9 4 4
6
4 1
5 7
6 1
0 7
6 2
8 7 9 10 4
6
3 2
4 5
0 3
1 4
3 4
5 1 9 5 4
2
3 2
4 4
9 1
0 1
3 4
5 4 12 3 0
6
3 1
3 4
9 1
2 7
6 2
5 2 9 4 4
6
4 1
5 7
9 1
0 7
6 2
8 7 9 10 4
6
3 2
4 5
0 3
1 4
3 6
5 1 9 5 4
2
3 2
3 4
9 1
0 1
3 4
5 4 12 3 0
6
3 1
3 4
9 1
2 7
6 2
5 3 9 6 4
6
4 1
5 7
9 1
0 7
6 2
8 7 9 5 4
2
3 2
3 2
9 1
0 1
3 4
5 4 12 3 0
6
3 1
3 4
9 1
2 7
6 2
10 3 9 5 4
2
3 3
3 2
9 1
0 1
3 4
5 4 12 3 0
6
3 1
2 4
9 1
2 7
6 2
10 3 9 5 4
2
3 3
3 2
9 1
0 1
3 4
9 4 9 5 4
2
3 3
3 2
9 1
0 1
3 4
10 4 9 5 4
2
3 3
3 2
9 1
0 1
3 4
0 4 9 5 4
2
3 3
3 2
10 1
0 1
3 4
0 4 9 5 4
2
3 3
3 2
10 1
0 1
5 4
0 4 11 5 4
2
3 3
3 2
10 1
0 1
5 4
0 4 11 5 4
2
3 3
3 2
10 2
0 1
5 4
0 4 11 5 4
2
5 3
3 2
10 2
0 1
5 4
0 4 11 5 4
2
5 1
3 2
10 2
0 1
5 4
0 4 11 5 4
0
5 1
3 2
10 2
0 1
5 4
0 4 11 5 4
0
10 1
3 2
10 2
0 1
5 4
0 4 11 5 4
0
10 1
3 2
10 2
0 0
5 4
0 4 11 5 4
0
10 1
3 2
10 2
0 0
5 4
0 5 11 5 4
0
10 1
3 0
10 2
0 0
5 4
0 5 11 5 4
0
10 1
3 0
10 4
0 0
5 4
0 5 11 5 4
0
10 1
3 0
10 4
0 0
5 4
0 8 11 5 4
0
10 0
3 0
10 4
0 0
5 4
0 8 11 5 4
0
10 0
3 0
10 4
0 0
5 4
0 7 11 8 4
0
10 0
3 0
10 4
0 0
5 4
0 7 11 8 1
0
10 0
3 0
10 4
0 0
5 4
0 7
6 -1
 10
 5
 9
 15
 6
 12
 3
 8
 11
 0
 10
 10
 -1
 10
 10
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 10
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 9
 15
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 9
 -1
 -1
 -1
 -1
 -1
 -1
 9
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
