JustifyWords

Problem Description

Given a list of K words and integers N and M, you are asked to arrange the words into N lines following the below rules.

• Each line can contain no more than M letters.
• Each word should present entirely on one line.
• If multiple words are on a line, they should be separated by a single space.

Find the maximum number of words you can arrange in the given lines of length M.

Constraints

0 < K < 25

0 < N < 10

0 < M < 10

Words will be having only lowercase alphabets.

Input

First line consists of an integer K denoting the total number of words.

Next K lines consist of words.

Last line consists of two space separated integers denoting the values of N and M.

Output

Print a single integer denoting the maximum number of words that can be arranged into the N lines.

Time Limit (secs)

1

Examples

Example 1

Input

8

i

hello

how

going

u

whatsapp

help

hmm

5 5

Output

7

Explanation

8 words need to be arranged in 5 lines each of length 5 characters.

One way to arrange the words to fit maximum words is as follows.

how_i

going

u_hmm

help_

hello_

where _ represents empty space. 7 words can be fitted. And that's the maximum possible. There could be other combinations i.e. [hello, help , going ,i u,hmm] etc., but we are interested in maximum number of words being accommodated in N lines each of length M.

Example 2

Input

6

a

is

b

be

it

a

5 4

Output

6

Explanation

6 words need to be arranged in 5 lines each of length 4 characters.

One way to arrange the words to fit maximum words is as follows.

a_is

b_be

it_a

____

where _ represents empty space. Here entire last line is empty. 6 words can be fitted and that's the maximum.