I Hate Ready to Program P3 - Test Case Limit Exceeded

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.5s
Python 2.5s
Memory limit: 256M

Author:
Problem type

You are trying to do an ICS assignment involving vowels and consonants but to your horror, it seems this stubborn old version of Java doesn't have String.contains()! Thus, you must check the characters of each string individually.

However, Ready to Program isn't going to make it this easy. There is only a maximum number of characters, N, it can read before it stops running. You have created a list of M words to test your program with. Since you want to be sure your program doesn't fail, you want to test as many words as possible. However, since you are low on time, and once RtP stops working, you are not going to go through the hassle of closing and reopening it again. What is the maximum number of words you can test?

Constraints

The length of strings s_1,s_2,s_3,...,s_M are less than or equal to 42 characters long.

Subtask 1 [30%]

1 \leq N,M \leq 10^3

Subtask 2 [70%]

1 \leq N,M \leq 10^7

Input Specifications

The first line will contain two space-separated integers, N and M.

The next M lines will contain a string, s_i each on its own line. The strings will have no spaces and only contain lowercase letters.

Output Specifications

Output an integer, P, the maximum number of words you can use before RtP stops running.

Sample Input

14 5
hi
ready
to
program
help

Sample Output

4

Sample Case Explanation

By using the words "to", "hi", "help", and "ready", the 4 words use 13 characters. You cannot use "program" as the sum of characters would reach 20, which is over the limit of 14 characters, and thus Ready to Program will explode stop working.


Comments

There are no comments at the moment.