def get_intersection(rect1, rect2):
    y1, x1, y2, x2 = rect1
    y3, x3, y4, x4 = rect2
    return (
        max(0, 1 + min(x4, x2) - max(x1, x3)) *
        max(0, 1 + min(y4, y2) - max(y1, y3))
    )

def solve_stupid(N, M, R, C, parks):
    min_trees = None
    best_pos = None
    for r in xrange(1, N - R + 2):
        for c in xrange(1, M - C + 2):
            trees = 0
            for park in parks:
                trees += get_intersection((r, c, r + R - 1, c + C - 1), park)
            if min_trees is None or min_trees > trees:
                min_trees = trees
                best_pos = (r, c)
    return min_trees, best_pos



def get_interesting(a1, a2, l, total):
    # growing starts at pos such that pos + l == a1
    grow_start = max(1, a1 - l)
    # growing stops at pos = a1
    grow_stop = a1

    # falling starts at pos such that pos + l - 1 = a2
    fall_start = max(1, a2 - l + 1)
    # falling stops at pos right after a2: pos = a2 + 1
    fall_stop = a2 + 1

    # squeeze coordinates that don't fit
    grow_start = min(grow_start, total)
    grow_stop = min(grow_stop, total)
    fall_start = min(fall_start, total)
    fall_stop = min(fall_stop, total)

    return grow_start, grow_stop, fall_start, fall_stop

def solve_smart(N, M, R, C, parks):
    interesting_rows = set([1])
    interesting_cols = set([1])

    for park in parks:
        r1, c1, r2, c2 = park
        interesting_rows.update(get_interesting(r1, r2, R, N - R + 1))
        interesting_cols.update(get_interesting(c1, c2, C, M - C + 1))

    rows = sorted(interesting_rows)
    cols = sorted(interesting_cols)

    col_to_index = {col: i for i, col in enumerate(cols)}

    min_trees = None
    best_pos = None
    for r in rows:
        deriv_changes = [0] * len(cols)
        for park in parks:
            r1, c1, r2, c2 = park
            gstart, gstop, fstart, fstop = get_interesting(c1, c2, C, M - C + 1)
            park_height = get_intersection(
                (r, c1, r + R - 1, c1),
                park
            )
            deriv_changes[col_to_index[gstart]] += park_height
            deriv_changes[col_to_index[gstop]] -= park_height
            deriv_changes[col_to_index[fstart]] -= park_height
            deriv_changes[col_to_index[fstop]] += park_height

        # now we know how derivative changes and we need
        # initial value to start with
        trees = 0
        first_col = cols[0]
        for park in parks:
            trees += get_intersection(
                park,
                (r, first_col, r + R - 1, first_col + C - 1)
            )

        if min_trees is None or min_trees > trees:
            min_trees = trees
            best_pos = (r, first_col)

        derivative = 0
        for i, col in enumerate(cols[:-1]):
            derivative += deriv_changes[i]
            next_col = cols[i + 1]
            trees += (next_col - col) * derivative
            if trees < min_trees:
                min_trees = trees
                best_pos = (r, next_col)

    return min_trees,  best_pos


solve = solve_smart

print solve_smart(5, 3, 2, 2, [
    (2, 2, 2, 2),
    (4, 2, 4, 2),
])

print solve_smart(5, 5, 3, 2, [
    (1, 1, 1, 5),
    (2, 1, 5, 1),
    (5, 2, 5, 5),
    (2, 5, 4, 5),
    (3, 3, 3, 4),
])


N = 100
M = 100
K = 50

import random

for R in xrange(1, N + 1):
    C = R
    parks = []
    for i in xrange(K):
        while True:
            r1 = random.randrange(1, N + 1)
            c1 = random.randrange(1, M + 1)
            r2 = random.randrange(r1, N + 1)
            c2 = random.randrange(c1, M + 1)
            new_park = (r1, c1, r2, c2)
            for park in parks:
                if get_intersection(new_park, park):
                    break
            else:
                parks.append(new_park)
                break

    smart = solve_smart(N, M, R, C, parks)
    stupid = solve_stupid(N, M, R, C, parks)
    if smart != stupid:
        print "FAIL"
        print smart
        print stupid
        print parks
        print N, M, R, C
        raise SystemExit