Maximum Contestants Assignment

You are given N restaurants and M contestants. Each restaurant \(c_j\) has a maximum capacity, and each contestant has dietary restrictions represented by a list of \(N\) binary values. A value of 1 indicates that the contestant can dine at that restaurant, while 0 means they cannot.

Your task is to determine the maximum number of contestants that can be assigned to the restaurants such that no restaurant is assigned more contestants than its capacity and each contestant is only assigned to a restaurant that meets their dietary restrictions.

inputFormat

The first line contains two integers \(N\) and \(M\), denoting the number of restaurants and contestants respectively.

The second line contains \(N\) integers. The \(j\text{-th}\) integer represents the capacity \(c_j\) of restaurant \(j\).

Each of the following \(M\) lines contains \(N\) binary integers (0 or 1) separated by spaces, representing the dietary restrictions of a contestant. The \(j\text{-th}\) number in a line is 1 if the contestant can dine at restaurant \(j\), otherwise it is 0.

outputFormat

Output a single integer: the maximum number of contestants that can be assigned to the restaurants according to the constraints.

3 4
2 3 1
1 0 0
0 1 1
1 1 0
0 1 1

4