## OCC '19 G1 - Top Coder

View as PDF

Points: 10
Time limit: 0.6s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 kinds of skills, conveniently numbered from to . Andrew's initial skill values are . To improve these skills, Andrew needs to practice a lot of questions. There are questions on the online judge. For the question, it requires kinds of skills . If each kind of Andrew's skill is not lower than the question required (i.e. , where ), Andrew can solve the question and improve his skill from the question, which means his skill will increase by ().

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

#### Input Specification

The first line contains two integers, and (, ), the number of questions and the number of skills.

The second line contains integers, (), Andrew's initial skill.

Each of the following lines contains integers, (), the skill required by the 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

3

#### Explanation to sample output

Andrew's initial skills are .

• Andrew can solve question which requires skills , and after that, Andrew's skills are .
• Andrew can solve question which requires skills , and after that, Andrew's skills are .
• Andrew can solve question which requires skills , and after that, Andrew's skills are .

However, Andrew cannot solve question , since it requires the skill with value of , but Andrew only has . So, Andrew can solve questions at most.

and .