🏡 index : github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: CALLSCHE
problem_name: 'Call Center Schedule'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYPY
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM chicken'
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: cenadar
problem_tester: iscsi
date_added: 19-12-2015
tags:
    - cenadar
    - feb16
    - graph
    - maxflow
    - medium
    - minimum
editorial_url: 'http://discuss.codechef.com/problems/CALLSCHE'
time:
    view_start_date: 1455528600
    submit_start_date: 1455528600
    visible_start_date: 1455528600
    end_date: 1735669800
    current: 1493557499
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/FEB16/mandarin/CALLSCHE.pdf), [Russian](http://www.codechef.com/download/translated/FEB16/russian/CALLSCHE.pdf) and [Vietnamese](http://www.codechef.com/download/translated/FEB16/vietnamese/CALLSCHE.pdf) 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 **Li** 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 **Ri,j** people talking with clients during the day **i** and hour **j**.

**Fk, 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 **LTbegin** to **LTend** 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 **Li** 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 **Ri,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 space-separated 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** space-separated integers, where the **ith** integer denotes **Li**.

The next line contains two space-separated integers **LTbegin** and **LTend**. The first integer denotes the first hour of the designate lunch period, and the second denotes its last hour.

Next **D** lines contain **H** space-separated integers each. The **jth** integer of line **i** denotes **Ri,j**.

Next **P** blocks of lines will contain **D** lines each, with a line containing **H** space-separated integers. The **jth** integer of line **i** of block **k** denotes **Fk,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** ≤ **Li** ≤ **N\*D**
- 0 ≤ **Ri,j** ≤ **15**
- 0 ≤ **Fk,i,j** ≤ **1**
- **1** ≤ **LTbegin, LTend** ≤ **N**

### Subtasks

- **Subtask #1 \[15 points\]: MAX = 3**
- **Subtask #2 \[25 points\]: MAX = 10**
- **Subtask #3 \[60 points\]: MAX = 70**

### Example

<pre><b>Input:</b>
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

<b>Output:</b>
Yes
No
</pre>