Recently, a gigantic blizzard has hit Mizore's homeland. Because of this, she has lost electricity in her house. To pass the time, she decides to build a snowman with her friends. The snow lies in patches on the ground. However, not all the snow is pure, and Mizore does not want to contaminate her snowman with dirty snow.
To make a snowball, Mizore needs a continuous horizontal or vertical strip of snow which has the same length in patches as the snowball's size. After using a strip of snow to make a snowball, the snow from that strip is then used up, so one patch of snow may not be used to build two different snowballs. While avoiding the dirty snow, please help Mizore determine if she can make her snowman or not.
The first line of input will contain 3 integers: ~M~, ~N~, and ~S~.
The next ~S~ lines will each contain a size of a snowball, ~B_i~.
The next ~M~ lines will each contain ~N~ characters, the description of the ground. Each character will be either a
0 or a
0 is used to indicate clean snow, and
1 is used to indicate dirty snow.
On a single line, output
yes if Mizore can build a snowman with only clean snow; otherwise, output
|Test Case Batch||Marks||Constraints|
|1 [15 cases]||20||~1 \le M, N \le 4; 1 \le S \le 3; 1 \le B_i \le 4~|
|2 [5 cases]||25||~1 \le M, N \le 5; 1 \le S \le 5; 1 \le B_i \le 5~|
|3 [5 cases]||25||~1 \le M, N \le 10; 1 \le S \le 5; 1 \le B_i \le 10~|
|4 [10 cases]||30||~1 \le M, N \le 10; 1 \le S \le 9; 1 \le B_i \le 10~|
Sample Input 1
3 4 3 1 2 3 0100 0111 0011
Sample Output 1
Explanation for Sample Input 1
Mizore can use the snow like this to build all three snowballs (
a being the smallest and
c being the largest).
c1bb c111 ca11
Sample Input 2
2 2 1 2 01 10
Sample Output 2
Explanation for Sample Input 2
No matter how Mizore assigns the pure snow, she cannot make a snowball of size 2, because the 2 patches of pure snow are connected neither horizontally nor vertically.