F. Reborn and TFT
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Reborn 最近沉迷云顶无法自拔。

她现在有 $$$n$$$ 个人口，牌库里总共有 $$$m$$$ 个棋子，每个棋子拥有若干个不同的羁绊，其中羁绊一共有 $$$k$$$ 种，每个羁绊至少需要 $$$x$$$ 个拥有该羁绊的不同棋子同时上场将其激活。

现在 Reborn 告诉你每个羁绊激活所需的棋子数量，以及牌库中每个棋子所拥有的羁绊，她只能从牌库中选择至多 $$$n$$$ 个棋子上场用于激活羁绊，请你告诉她最多能激活几个羁绊。

Input

第一行包含三个整数 $$$n, m, k\ (1 \le n, m \le 28, 1 \le k \le 14)$$$。

第二行包含 $$$k$$$ 个整数 $$$x_1, x_2, ..., x_k\ (1\le x_i \le 2)$$$，其中第 $$$i$$$ 个整数 $$$x_i$$$ 表示第 $$$i$$$ 个羁绊需要 $$$x_i$$$ 个不同棋子同时上场才可以激活。

接下来 $$$m$$$ 行每行包含一个字符串 $$$s\ (|s| = k, s_i \in \{'0', '1'\})$$$ 表示该棋子所拥有的羁绊，其中 $$$|s|$$$ 表示字符串的长度，若 $$$s_i = '1'$$$ 说明该棋子拥有第 $$$i$$$ 个羁绊。

Output

输出一行包含一个整数，表示所能激活的最多羁绊数量。

Example
Input
1 2 4
1 1 2 2
0011
1100
Output
2