Under construction

Still being built. Things may change

Want to ensemble?

Interview

Time limit1sMemory limit512 MB

Summary
Given predictions from N models on M items, check whether some odd-sized group of models, combined by majority vote, beats the most accurate single model.
Level

Easy3 of 10

Topics
Brute force, Bit manipulation
Solved
No attempts yet

Problem

To celebrate the opening of the Artificial Intelligence department at Seoul Cyber University, Professors Noh and Cheon assigned each student to build one binary classification AI model. While evaluating the models, the two professors wondered whether combining them into an ensemble could improve performance. An ensemble combines the outputs of several models. This time they decided to try hard voting, where for each prediction item the value output by the most models becomes the final result. In this problem, the ensemble uses an odd number of models.

For example, suppose the answers for six prediction items are [0,1,0,1,1,0][0, 1, 0, 1, 1, 0], and the predictions from four students' models are as follows.

  • Student 1: [1,0,0,1,1,0][1, 0, 0, 1, 1, 0]
  • Student 2: [0,1,1,1,1,0][0, 1, 1, 1, 1, 0]
  • Student 3: [0,1,0,0,0,0][0, 1, 0, 0, 0, 0]
  • Student 4: [0,0,1,0,1,0][0, 0, 1, 0, 1, 0]

If the models of Students 1, 2, and 4 are selected and combined by hard voting, the result is [0,0,1,1,1,0][0, 0, 1, 1, 1, 0]. Checking each item:

  • Item 1: 0 appears twice and 1 appears once, so the final prediction is 0.
  • Item 2: 0 appears twice and 1 appears once, so the final prediction is 0.
  • Item 3: 0 appears once and 1 appears twice, so the final prediction is 1.
  • Item 4: 0 appears once and 1 appears twice, so the final prediction is 1.
  • Item 5: 0 does not appear and 1 appears three times, so the final prediction is 1.
  • Item 6: 0 appears three times and 1 does not appear, so the final prediction is 0.

The ensemble result is compared with the answers. Four of the six items match, so the accuracy is 46\frac{4}{6}.

If some ensemble combination has higher accuracy than the single most accurate model, the ensemble is judged to improve performance. Check whether such a combination exists.

Input

The first line contains the number of models NN and the number of prediction items MM. (1≤N≤16;(1 \le N \le 16; 1≤M≤100)1 \le M \le 100)

The second line contains the correct answers for the MM prediction items, in order.

From the third line onward, NN lines give the predictions of each model for the MM items, in order.

All answers and predictions are either 00 or 11, separated by spaces.

Output

On the first line, print 1 if there is a combination whose hard-voting ensemble has higher accuracy than the single most accurate model. Otherwise, print 0.

Examples2

  1. Example 1

    Input
    4 6
0 1 0 1 1 0
1 0 0 1 1 0
0 1 1 1 1 0
0 1 0 0 0 0
0 0 1 0 1 0
    Expected output
    1

  2. Example 2

    Input
    4 6
0 1 0 1 1 0
1 0 1 0 0 0
0 1 1 0 1 0
1 1 0 1 0 0
0 0 1 0 1 0
    Expected output
    0