Efficient Weekly Employee Scheduling

In this problem, you are given a weekly scheduling problem in a rather unusual world. A company works for D days in a week (numbered 1 through D) and each day has H working hours available for client calls. Each hour an employee must devote exactly one activity: either attend a pre‐scheduled meeting, answer a client call (if no meeting is scheduled) or work on a research project. Note that if an employee is not scheduled for a meeting or a client call during some hour, he/she can work on a research project (which counts as working time) but may also take time for personal research (which does not count).

There are several constraints:

1. For each employee, the meeting schedule is fixed. For every employee k on day i during hour j, you are given a value F_k,i,j where F_k,i,j = 0 means a meeting is scheduled (and the employee must attend) and F_k,i,j = 1 means there is no meeting so the employee is free.
2. The call centre has H specific hours in each day (hours 1 through H) during which client calls can be answered. For each day i and hour j (1 ≤ j ≤ H), exactly R_i,j employees must answer a client call.
3. For each employee k, in any day, the total number of hours spent in meetings or answering calls must not exceed N. (Research on projects does not count towards this daily limit.) Note that for an employee k on day i, the number of meeting hours is predetermined (i.e. the count of j for which F_k,i,j = 0) so he/she can answer calls in at most [N - (number of meeting hours on day i)] free hours.
4. For each employee k, over the entire week, the total number of hours answering client calls must not exceed a given limit L_k.
5. There is a lunch break every day: from hour L_{T_begin} to L_{T_end} (inclusive). In each day, every employee must have at least one lunch hour during which he/she is not answering a client call (even if no meeting is scheduled, that hour must be left for rest or meal).

Your task is to decide whether it is possible to assign, for every free hour (i.e. F_k,i,j=1), an activity (either answering a client call or working on a company research project) so that:

• For every day i and hour j (from 1 to H), exactly R_i,j employees are assigned to answer client calls.
• For every employee and day, the number of hours with meetings plus the number of hours answering calls does not exceed N.
• For every employee, the total client call hours for the week does not exceed L_k.
• For every employee and every day, during the lunch break [L_{T_begin}, L_{T_end}], there is at least one hour in which the employee is not answering a client call (if free this hour, they can work on the company project instead).
</p>

If it is possible to create such a schedule, output YES; otherwise, output NO.

Note on Input: The meeting schedule is given as a binary string for each employee for every day. A character '0' means a meeting is scheduled for that hour (and cannot be changed) and a '1' means the employee is free in that hour.

inputFormat

The input begins with a line containing four integers: M D H N where

• M is the number of employees.
• D is the number of days in the week.
• H is the number of working hours (and client call available hours) per day.
• N is the maximum number of hours per day an employee may spend in meetings or on client calls.

The second line contains M integers, where the k^th integer is L[k] – the maximum number of client call hours employee k may work in the week.

The third line contains two integers: L_T_begin and L_T_end, denoting the start and end hours (inclusive) of the lunch break.

Then follow D lines, each containing H integers. The i^th of these lines contains the integers R[i,1], R[i,2], ..., R[i,H], where R[i,j] is the exact number of employees that must be assigned to a client call on day i during hour j.

After that, for each employee k (1 ≤ k ≤ M), there are D lines (one per day). Each of these lines is a binary string of length H. The j^th character of the string for day i is:

• '0' if employee k has a meeting at day i, hour j.
• '1' if employee k is free at day i, hour j (and hence can be assigned to either a client call or a research project during that hour).

All numbers and strings are separated by whitespace or newline.

outputFormat

Output a single line containing YES if a valid schedule exists; otherwise, output NO.

sample

2 2 3 2
2 2
2 3
1 1 0
1 0 1
101
111
111
111

YES