У Кости есть текст \(s\) из \(n\) слов, состоящих из букв латинского алфавита. Также у него есть две полоски, на которые он должен выписать текст. На первую полоску помещается \(m\) символов, а на вторую — сколько угодно.
Костя должен выбрать число \(x\) и выписывает первые \(x\) слов из \(s\) на первую полоску, а все остальные — на вторую. Ради экономии места слова выписываются без отступов, но каждое слово должно полностью быть на одной полоске.
Так как место на второй полоске очень ценно, Костя просит вас выбрать максимальное возможное число \(x\), чтобы все слова \(s_1, s_2, \dots, s_x\) уместились на первую полоску длины \(m\).
Выходные данные
Для каждого набора входных данных выведите максимальное число слов \(x\), такое что первые \(x\) слов имеют суммарную длину не больше \(m\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 1
a
b
c
2 9
alpha
beta
4 12
hello
world
and
codeforces
3 2
ab
c
d
3 2
abc
ab
a
|
1
2
2
1
0
|