Floor Distribution

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef just come up with a very good idea for his business. He needs to hire two group of software engineers. Each group of engineers will work on completely different things and people from different groups don't want to disturb (and even hear) each other. Chef has just rented a whole floor for his purposes in business center "Cooking Plaza". The floor is a rectangle with dimensions N over M meters. For simplicity of description the floor's structure, let's imagine that it is split into imaginary squares of size 1x1 called "cells".
The whole floor is split into rooms (not necessarily rectangular). There are some not noiseresistant walls between some of the cells. Two adjacent cells belong to the same room if they don't have the wall between them. Cells are considered adjacent if and only if they share an edge. Also, we say that relation "belong to the same room" is transitive. In other words we say that if cells A and B belong to the same room and B and C belong to the same room then A and C belong to the same room.
So we end up having a partition of the floor into rooms. It also means, that each point on the floor belongs to some room.
Chef have to distribute the rooms between engineers of two groups. Engineers from the different groups cannot seat in the same room. If engineers from a different groups seat in adjacent rooms, the walls these rooms share have to be noiseresistant. The cost of having one meter of wall isolated is I per month. Due to various reasons Chef has to pay an additional cost for support of each of the room (e.g. cleaning costs money as well). Interesting to know that support cost for a particular room may differ depending on engineers of which group seat in this room.
Chef doesn't know the number of people he needs in each group of engineers so he wants to minimize the money he needs to pay for all the floor rent and support. He will see how it goes and then redistribute the floor or find another floor to rent or whatever. Either way, you don't need to care about this.
Please pay attention to the restriction that all the rooms should be occupied by engineers of one of the teams. Also, it might happen that all the rooms will be assigned to the same team and this is completely okay.
Input
The first line of the input contains three integers N, M, W, K and R, where N and M denote size of the floor, W denote number of onemeterlength walls, K denote cost of having onemeterlength wall be noiseresistant and R denote the number of rooms in which floor is partitioned.
Next W lines contain four integers each X_{1}, Y_{1}, X_{2}, Y_{2}. This means that cells with coordinates X_{1}, Y_{1} and X_{2}, Y_{2} have a wall between them. It's guaranteed that this cells share an edge.
Next R lines will contain four space separated integers each X, Y, C_{1}, C_{2}. This should be treated as support cost per month in a room that contain cell X, Y is C_{1} for first group of engineers and C_{2} for second group of engineers. It's guaranteed that all of cells among these R cells belong to different rooms. All coordinates are indexed starting from 1.
Output
Output a single integer  sum of the rent and support costs per month.
Constraints
 1 ≤ N, M ≤ 1000
 1 ≤ W ≤ min(2*N*M, 150000)
 1 ≤ X_{1} ≤ N
 1 ≤ Y_{1} ≤ M
 1 ≤ X_{2} ≤ N
 1 ≤ Y_{2} ≤ M
 1 ≤ K ≤ 10000
 1 ≤ C_{1}, C_{2} ≤ 10000
 Limitations on R is described in subtasks section.
Subtasks
 Subtask #1 [30 points]: 1 ≤ R ≤ 50
 Subtask #2 [70 points]: 1 ≤ R ≤ 500
Example
Input: 2 4 5 5 3 1 2 1 3 1 2 2 2 1 3 2 3 1 4 2 4 2 1 2 2 1 1 30 12 1 3 10 15 2 3 11 22 Output: 48
Explanation
Here's the scheme of the floor
The correct assignment is the following.
 The blue color denotes assignment to the first team. Total cost for renting two rooms for this team is 11 + 10 = 21.
 The red color denotes assignment to the second team. Total cost for renting the only room for the team is 12.
 There are 3 meters of walls between them, resulting in isolating cost of 15.
The grand total is 21 + 12 + 15 = 48
Author:  cenadar 
Tester:  furko 
Editorial  http://discuss.codechef.com/problems/FLOORDIS 
Tags  cenadar, march16, maxflow, medium, mincutmaxflow, minimumcut 
Date Added:  1122015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 