Problem Description

Mr. R is practicing typing.

There is a typing practice website. Given a reference text and an input box, it will calculate your accuracy and typing speed based on what you type. The characters you can type are lowercase letters, spaces, and . (a period). After you type a character, the cursor moves accordingly.

The typed text has multiple lines. Mr. R can press the Enter key to start a new line, and after that the cursor moves to the beginning of the next line.

Mr. R can also press the Backspace key (for convenience, we use < to represent Backspace) to delete the previously typed character and move the cursor back by one position. In particular, if the cursor is already at the beginning of a line, you cannot backspace anymore (i.e., ignore this Backspace input).

The website compares texts according to the following two rules:

• Compare line by line: compare each line of the reference text and the input in order. Different lines do not affect each other, and extra lines are ignored.
• Compare position by position: for each character position in a line, compare in order. A character is counted as correct if and only if the characters are the same; otherwise it is counted as wrong. When computing the result, only the number of matching characters is counted.

Note that the Enter key is not included in the number of correct characters.

Mr. R sees that the website shows he spent $T$ seconds to finish this typing game. Please compute his KPM (Keys per minutes, the number of characters entered per minute). Round the answer to the nearest integer.

Input Format

Mr. R will provide you with the reference text, his input, and the time spent, in this order.

The reference text and the input are read as follows: given several lines of strings, ending with a single line EOF. The line EOF is not part of the text.

The last line is an integer $T$, meaning he spent $T$ seconds typing.

You may refer to the sample input/output files and the sample explanation for better understanding.

Output Format

Output one integer on a single line, representing the KPM.

hello world.
aaabbbb
x
EOF
heelo world.
aaacbbbb
y<x
EOF
60

18

Hint

Sample Explanation

The number of correct characters in the first line is 11.
The number of correct characters in the second line is 6. The wrong character c still takes up one position.
The number of correct characters in the third line is 1. Mr. R used Backspace to delete the incorrectly typed character y.

Constraints

For $20\%$ of the testdata, there is no Enter key.
For $40\%$ of the testdata, there is no Backspace key.
For $100\%$ of the testdata, $T \leq 10^3$, and the total number of characters (including newlines) in each text block is at most $10^5$, and the total number of lines is at most $10^4$.

Translated by ChatGPT 5