Escapism
Limits: 2 sec., 512 MiB
Zenyk wrote a sentence of words made of lowercase Latin letters. Adjacent words are separated by exactly one space, and there are no spaces at the beginning or at the end of the sentence.
Marichka noticed that the text editor escapes the text when it is
pasted. In one operation, one more backslash \ is added in
front of every space and in front of every backslash \. All
these changes happen simultaneously: the characters added during an
operation are escaped only by the following operations. No other
characters change.
For example, after the first paste hello algotester
becomes hello\ algotester, and after the second paste it
becomes hello\\\ algotester.
Find the smallest number of such operations after which the length of the text becomes greater than \(n\). Every letter, space and backslash counts as one character.
Input
The first line contains one integer \(n\) – the bound on the length of the text.
The second line contains the sentence \(s\).
Output
Print one integer – the smallest number of operations after which the length of the text becomes greater than \(n\).
If the initial length of the text is already greater than \(n\), print 0. If the length of the text
never becomes greater than \(n\), print
-1.
Constraints
\(1 \le n \le 10^9\),
\(1 \le |s| \le 10^5\),
the sentence consists of one or more words made of lowercase Latin letters,
adjacent words are separated by exactly one space, and there are no spaces at the beginning or at the end of the sentence.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 17 hello algotester | 2 |
| Input (stdin) | Output (stdout) |
|---|---|
| 3 a b | 1 |
| Input (stdin) | Output (stdout) |
|---|---|
| 2 abc | 0 |
| Input (stdin) | Output (stdout) |
|---|---|
| 10 abc | -1 |
Notes
In the first example, the initial length of the sentence is 16. After the first operation it is 17, and after the second one it is 19. So two operations are needed.
In the second example, the length changes from 3 to 4 after one operation.
In the third example, the initial length is already greater than \(n\).
In the fourth example, the sentence has no spaces, so its length never changes.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|