B. Bank
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A bank maintains a log of money transfer operations. Each log entry consists of three elements recorded in binary code in the following order:

  • The sender's identifier — a non-negative integer of arbitrary length without leading zeros,
  • The recipient's identifier — a non-negative integer of arbitrary length without leading zeros,
  • The transfer amount — a positive integer without leading zeros, containing no more than $$$K$$$ digits.

The sender's and recipient's identifiers cannot be the same. The bank's identifier is equal to $$$0$$$.

Due to an unfortunate coincidence a day before the bank's license was revoked, all delimiters were removed from the log, and all paper copies of transfers were destroyed.

Your task is to restore the delimiters between the entries and the elements of the entries so that the net increase in the bank's account is maximized.

Input

The first line of the input file contains an integer $$$K$$$ ($$$1 \leq K \leq 45$$$). The second line contains the log of operations represented as a string of '0' and '1'. The length of the log is at least $$$4$$$ and at most $$$100\,000$$$ characters. It is guaranteed that there exists at least one way to place the delimiters.

Output

Output the maximum net increase in the bank's account.

Examples
Input
1
11011011
Output
1
Input
4
011000
Output
-8
Input
1
111011
Output
0
Note

In the first example, the optimal separation is $$$11\;0\;1\;10\;1\;1$$$: client $$$11_2$$$ transferred 1 unit of currency to the bank, after which client $$$10_2$$$ transferred 1 unit to client $$$1_2$$$.

In the second example, the separation is $$$0\;1\;1000$$$: the bank transferred 8 units of currency to client $$$1_2$$$.

In the third example, the separation is $$$11\;101\;1$$$: client $$$11_2$$$ transferred money to client $$$101_2$$$. The bank's balance remained unchanged.