Optimal Channel Partitioning

In a classroom, students are arranged in an M×N grid. Each student sits at a position (i, j) where 1 ≤ i ≤ M and 1 ≤ j ≤ N. It is known that exactly D pairs of students tend to chat during class. To help manage the classroom, there are K horizontal passages and L vertical passages available, which can be placed between adjacent rows or columns of desks. Note that a passage placed between row r and r+1 separates any two students if one sits in a row ≤ r and the other in a row ≥ r+1. Similarly, a vertical passage placed between column c and c+1 separates students sitting in columns ≤ c and those in columns ≥ c+1.

A pair of students will be able to chat if and only if both of the following conditions hold:

• No horizontal passage is placed between their respective rows. In other words, if the two students are at rows r₁ and r₂ (assume r₁ ≤ r₂), then there is no chosen horizontal passage at any row index h with r₁ ≤ h < r₂.
• No vertical passage is placed between their respective columns. That is, if they are at columns c₁ and c₂ (with c₁ ≤ c₂), then there is no chosen vertical passage at any column index v with c₁ ≤ v < c₂.

Your task is to help the teacher find an optimal placement for the passages. You are allowed to choose exactly K out of the M − 1 possible horizontal gaps (between consecutive rows) and exactly L out of the N − 1 possible vertical gaps (between consecutive columns). Under the optimal placement, determine the minimum number of chatting pairs that remain able to chat during class.

Note: If a passage separates a chatting pair, they no longer chat regardless of any other channels.

inputFormat

The first line contains five space‐separated integers: M, N, K, L, and D.

• M and N (1 ≤ M, N) represent the numbers of rows and columns respectively.
• K is the number of horizontal passages to be placed (you must select exactly K gaps out of the M − 1 available).
• L is the number of vertical passages to be placed (you must select exactly L gaps out of the N − 1 available).
• D is the number of chatting pairs.

Each of the following D lines contains four integers r₁, c₁, r₂, c₂ which denote the positions of a chatting pair. The positions may be given in any order. It is guaranteed that the positions are within the grid.

outputFormat

Output a single integer: the minimum number of chatting pairs that remain able to chat after optimally placing the passages.

sample

3 3 1 1 2
1 1 2 2
2 3 3 3

0