Call Center Schedule

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is working as a manager of a call center. He has a large number of empoyees in his team. Each of them spends their time participating in meetings, talking to clients over the phone, and a few other activities related to the job.
Each person can spend an hour either in a meeting, talking to clients, or working on their project. Each hour must be dedicated to only one activity and in a single hour, a person cannot switch activities.
There are D business days in the week, numbered 1 to D. Person i can spend at most L_{i} hours per week talking to clients. For each person, it is known which hours in their schedule are taken up by meetings.
The call center responds to client for H hours per day, which, for simplicity, are numbered 1 through H.
For each hour in the week, the number of clients connecting to the call center for that hour is known. So, Chef knows that he needs exactly R_{i,j} people talking with clients during the day i and hour j.
F_{k, i, j} is equal to 1 if person k is available to talk to clients during hour j of day i and 0 if they have a meeting during that time.
Please note that Chef lives in an alien world, which may not have 24 hours in a day or 7 days in a week.
Chef needs to create a schedule for each person. Remember that there is a lunch period every day, from LT_{begin} to LT_{end} hours, both inclusive , so please make sure that each person will have at least one hour of free time during the designated lunch period.
If some person doesn't have a meeting during an hour and they don't talk to a client as well during that hour, they can work on a corporate project and this hour will count as a working hour. Alternatively, they may spend this time working on a personal project and it will not count as a working hour.
Please help Chef find out if it is possible to create a schedule such that following conditions hold.
 Each person spends at most N hours per day being on meetings and speaking with clients.
 Each person spends at most L_{i} hours per week talking to clients.
 Each person has at least one hour during the lunch time free of client calls as well as meetings.
 For each hour j on the day i, there are exactly R_{i,j} people free to talk to clients.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case input contains four spaceseparated integers — P, D, H and N — denoting the number of people in the team, number of working days in a week, number of hours the call center works in a day, and the number of working hours per day for people respectively.
The next line contains P spaceseparated integers, where the i^{th} integer denotes L_{i}.
The next line contains two spaceseparated integers LT_{begin} and LT_{end}. The first integer denotes the first hour of the designate lunch period, and the second denotes its last hour.
Next D lines contain H spaceseparated integers each. The j^{th} integer of line i denotes R_{i,j}.
Next P blocks of lines will contain D lines each, with a line containing H spaceseparated integers. The j^{th} integer of line i of block k denotes F_{k,i,j}.
Output
For each test case in a single line output "Yes" (without quotes) if it's possible to create a schedule and "No" (without quotes) otherwise.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ H ≤ MAX
 1 ≤ D ≤ MAX
 1 ≤ P ≤ MAX
 1 ≤ L_{i} ≤ N*D
 0 ≤ R_{i,j} ≤ 15
 0 ≤ F_{k,i,j} ≤ 1
 1 ≤ LT_{begin}, LT_{end} ≤ N
Subtasks
 Subtask #1 [15 points]: MAX = 3
 Subtask #2 [25 points]: MAX = 10
 Subtask #3 [60 points]: MAX = 70
Example
Input: 2 2 2 3 2 4 1 2 3 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 2 2 3 2 4 1 2 3 0 1 2 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 Output: Yes No
Author:  cenadar 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/CALLSCHE 
Tags  cenadar, feb16, graph, maxflow, medium, minimumcut 
Date Added:  19122015 
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