OCC '19 G1 - Top Coder

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 512M

Problem types

Little Andrew has a dream: to be a top coder. A top coder must have a number of skills, like algorithm design, time complexity analysis, logic thinking, coding and debugging, etc.

Andrew designed a model for how to become a top coder. In his model, a top coder needs to master k kinds of skills, conveniently numbered from 1 to k. Andrew's initial skill values are a_1, a_2, \dots, a_k. To improve these skills, Andrew needs to practice a lot of questions. There are N questions on the online judge. For the i^{th} question, it requires k kinds of skills v_{i,1}, v_{i,2}, \dots, v_{i, k}. If each kind of Andrew's skill is not lower than the question required (i.e. a_j \ge v_{i,j}, where 1 \le j \le k), Andrew can solve the question and improve his skill from the question, which means his j^{th} skill will increase by v_{i,j} (1 \le j \le k).

Given Andrew's initial skills and the skills required by each question, can you help Andrew find out the most number of questions he can solve?

Input Specification

The first line contains two integers, N and k (1 \le N \le 10^5, 1 \le k \le 10), the number of questions and the number of skills.

The second line contains k integers, a_j (1 \le a_j \le 10^9), Andrew's j^{th} initial skill.

Each of the following N lines contains k integers, v_{i,j} (1 \le v_{ij} \le 10^9), the j^{th} skill required by the i^{th} question.

Output Specification

Print one integer, the most number of questions Andrew can solve.

Sample Input

4 3
5 3 1
4 2 1
2 3 7
9 4 2
3 9 2

Sample Output


Explanation for Sample Output

Andrew's initial skills are [5, 3, 1].

  • Andrew can solve question 1 which requires skills [4, 2, 1], and after that, Andrew's skills are [9, 5, 2].
  • Andrew can solve question 3 which requires skills [9, 4, 2], and after that, Andrew's skills are [18, 9, 4].
  • Andrew can solve question 4 which requires skills [3, 9, 2], and after that, Andrew's skills are [21, 18, 6].

However, Andrew cannot solve question 2, since it requires the 3^{rd} skill to have a value of 7, but Andrew only has 6. So, Andrew can solve 3 questions at most.


1 \le N \le 10^5 and 1 \le k \le 10.

Subtask Points Additional constraints
1 17 N \le 2\,000
2 18 k = 2
3 65 No additional constraints.


There are no comments at the moment.