Vasya plays Robot Bicorn Attack.

The game consists of three rounds. For each one a non-negative integer amount of points is given. The result of the game is the sum of obtained points. Vasya has already played three rounds and wrote obtained points one by one (without leading zeros) into the string s. Vasya decided to brag about his achievement to the friends. However, he has forgotten how many points he got for each round. The only thing he remembers is the string s.

Help Vasya to find out what is the maximum amount of points he could get. Take into account that Vasya played Robot Bicorn Attack for the first time, so he could not get more than 1000000 (106) points for one round.

Input

The only line of input contains non-empty string s obtained by Vasya. The string consists of digits only. The string length does not exceed 30 characters.

Output

Print the only number — the maximum amount of points Vasya could get. If Vasya is wrong and the string could not be obtained according to the rules then output number -1.

Examples

Input

1234


Output

37


Input

9000


Output

90


Input

0009


Output

-1

Note

In the first example the string must be split into numbers 1, 2 and 34.

In the second example the string must be split into numbers 90, 0 and 0. 

In the third example the string is incorrect, because after splitting the string into 3 numbers number 00 or 09 will be obtained, but numbers cannot have leading zeroes.

Difficulty: MEDIUM
Tags: Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
def f(t, k, s):
	if k == 1:
		if t[0] == '0' and len(t) > 1:
			return -1
		d = int(t)
		if d > 1000000:
			return -1
		return s + d
	if t[0] == '0':
		return f(t[1:], k - 1, s)
	p = [(t[i:], int(t[:i])) for i in range(1, len(t) + 2 - k)]
	return max((f(a, k - 1, s + b) for (a, b) in p if b < 1000001))
t = input()
print(-1 if len(t) < 3 else f(t, 3, 0))


import sys
[s] = sys.stdin.read().split()

def isvalid(s):
	if s == '0' or s == '1000000':
		return True
	if s[0] == '0' or len(s) > 6:
		return False
	return True
mx = -1
for i in range(1, len(s)):
	for j in range(i + 1, len(s)):
		s1 = s[0:i]
		s2 = s[i:j]
		s3 = s[j:]
		if isvalid(s1) and isvalid(s2) and isvalid(s3):
			a = int(s1)
			b = int(s2)
			c = int(s3)
			mx = max(mx, a + b + c)
print(mx)


def getscore(a, b, c):
	if len(a) > 1 and a[0] == '0' or (len(b) > 1 and b[0] == '0') or (len(c) > 1 and c[0] == '0'):
		return -1
	if int(a) > 1000000 or int(b) > 1000000 or int(c) > 1000000:
		return -1
	else:
		return int(a) + int(b) + int(c)
s = input()
maxsc = -1
for i in range(1, len(s) - 1):
	for j in range(i + 1, len(s)):
		a = s[:i]
		b = s[i:j]
		c = s[j:]
		score = getscore(a, b, c)
		if score > maxsc:
			maxsc = score
print(maxsc)


def main():
	mode = 'filee'
	if mode == 'file':
		f = open('test.txt', 'r')
	get = lambda : [str(x) for x in (f.readline() if mode == 'file' else input()).split()]
	[g] = get()
	n = len(g)
	maxx = -1
	for i in range(1, n - 1):
		for j in range(i + 1, n):
			x = g[:i]
			y = g[i:j]
			z = g[j:]
			if int(x) > 10 ** 6 or int(y) > 10 ** 6 or int(z) > 10 ** 6 or (len(x) > 1 and x[0] == '0') or (len(y) > 1 and y[0] == '0') or (len(z) > 1 and z[0] == '0'):
				continue
			maxx = max(maxx, int(x) + int(y) + int(z))
	print(maxx)
	if mode == 'file':
		f.close()
main()


s = input()
a = -1
for i in range(1, len(s) - 1):
	for j in range(i + 1, len(s)):
		x = int(s[:i])
		y = int(s[i:j])
		z = int(s[j:])
		if s[0] == '0' and len(s[:i]) > 1:
			continue
		if s[i] == '0' and len(s[i:j]) > 1:
			continue
		if s[j] == '0' and len(s[j:]) > 1:
			continue
		if x > 1000000.0 or y > 1000000.0 or z > 1000000.0:
			continue
		a = max(a, x + y + z)
print(a)


s = input()
final = -1
n = len(s)
flag = []
l = ['00', '01', '02', '03', '04', '05', '06', '07', '08', '09']
for i in range(1, n):
	for j in range(i + 1, n):
		numbers = [s[:i], s[i:j], s[j:]]
		if str(s[:i][:2]) in l or str(s[i:j][:2]) in l or str(s[j:][:2]) in l:
			flag.append(1)
		elif int(s[:i]) <= 1000000 and int(s[i:j]) <= 1000000 and (int(s[j:]) <= 1000000):
			final = max(final, int(s[:i]) + int(s[i:j]) + int(s[j:]))
			flag.append(0)
if len(set(flag)) == 1 and set(flag) == {1}:
	print(-1)
else:
	print(final)


def g(a):
	return (len(a) == 1 or a[0] != '0') and int(a) <= 1000000

def f(a, b, c):
	return int(a) + int(b) + int(c) if g(a) and g(b) and g(c) else -1
(s, v) = (input(), -1)
for i in range(1, len(s) - 1):
	for j in range(i + 1, len(s)):
		v = max(v, f(s[:i], s[i:j], s[j:]))
print(v)


def bad(s):
	if len(s) > 1 and s[0] == '0':
		return False
	if int(s) > 1000000:
		return False
	return True
s = input()
n = len(s)
ans = -1
for i in range(1, n + 1):
	for j in range(i + 1, n):
		if bad(s[:i]) and bad(s[i:j]) and bad(s[j:]):
			ans = max(ans, int(s[:i]) + int(s[i:j]) + int(s[j:]))
print(ans)


def get_all(s):
	return ((s[:i], s[i:j], s[j:]) for i in range(1, len(s)) for j in range(i + 1, len(s)))

def _map(pred, a):
	for _a in a:
		yield pred(_a)
is_in_range = lambda x: int(x) <= 1000000
is_not_multizero = lambda x: int(x) > 0 or len(x) == 1
not_start_with_zero = lambda x: x == '0' or (int(x) > 0 and (not x.startswith('0')))
pred = lambda x: all(_map(is_in_range, x)) and all(_map(is_not_multizero, x)) and all(_map(not_start_with_zero, x))
s = input('')
res = filter(pred, get_all(s))
x = list(_map(lambda x: sum(_map(int, x)), res))
print(max(x) if x else -1)


import sys
import math
from heapq import *
input = sys.stdin.readline
from functools import cmp_to_key

def pi():
	return int(input())

def pl():
	return int(input(), 16)

def ti():
	return list(map(int, input().split()))

def ts():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
mod = 1000000007
f = []

def fact(n, m):
	global f
	f = [1 for i in range(n + 1)]
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % m

def fast_mod_exp(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b = b >> 1
	return res

def inverseMod(n, m):
	return fast_mod_exp(n, m - 2, m)

def ncr(n, r, m):
	if n < 0 or r < 0 or r > n:
		return 0
	if r == 0:
		return 1
	return f[n] * inverseMod(f[n - r], m) % m * inverseMod(f[r], m) % m

def main():
	A()

def A():
	s = input()[:-1]
	if len(s) > 21 or len(s) < 3:
		print(-1)
		return
	mx = 0
	f = 0
	for i in range(len(s) - 2):
		for j in range(i + 1, len(s) - 1):
			a = s[0:i + 1]
			b = s[i + 1:j + 1]
			c = s[j + 1:len(s)]
			if (a[0] != '0' or len(a) == 1) and (b[0] != '0' or len(b) == 1) and (c[0] != '0' or len(c) == 1) and (int(a) <= 1000000 and int(b) <= 1000000 and (int(c) <= 1000000)):
				f = 1
				mx = max(mx, int(a) + int(b) + int(c))
	if f == 0:
		print(-1)
	else:
		print(mx)
main()


s = input()
ans = -1
for i in range(1, len(s)):
	for j in range(i + 1, len(s)):
		s_ = [s[:i], s[i:j], s[j:]]
		good = True
		for t in s_:
			if str(int(t)) != t:
				good = False
		for t in s_:
			if int(t) > 10 ** 6:
				good = False
		if good:
			ans = max(ans, sum(map(int, s_)))
print(ans)


s = input()

def valid(s):
	if not (s[0] == '0' and len(s) > 1) and int(s) <= 1000000:
		return True
	return False
res = []
for x in range(1, len(s)):
	for y in range(x, len(s)):
		b = [x, y]
		num1 = s[:x]
		num2 = s[x:y]
		num3 = s[y:]
		if len(set(b)) != 2:
			continue
		if valid(num1) and valid(num2) and valid(num3):
			res.append(int(num1) + int(num2) + int(num3))
if not len(res):
	print(-1)
else:
	print(max(res))


def convert(s):
	if s[0] == '0' and (not len(s) == 1):
		return -10000000000
	res = 0
	for i in s:
		res = res * 10 + int(i)
	if res > 10 ** 6:
		return -1000000000
	return res
s = input()
res = -1
for i in range(1, len(s) - 1):
	for j in range(i + 1, len(s)):
		res = max(res, convert(s[:i]) + convert(s[i:j]) + convert(s[j:]))
print(res)


s = input()
n = len(s)
ans = -1

def good(ss):
	if len(ss) > 1 and ss[0] == '0':
		return False
	if int(ss) > 1000000:
		return False
	return True

def valid(s0, s1, s2):
	return good(s0) and good(s1) and good(s2)
for i in range(1, n):
	for j in range(i + 1, n):
		if valid(s[:i], s[i:j], s[j:]):
			ans = max(ans, int(s[:i]) + int(s[i:j]) + int(s[j:]))
print(ans)


def test(s):
	if len(s) > 1:
		if s[0] == '0':
			return False
	if int(s) > 10 ** 6:
		return False
	else:
		return True
s = input()
k = len(s)
u = [-1]
for i in range(1, k):
	for j in range(1, k):
		if s[i + j:] != '':
			if test(s[:i]) and test(s[i:i + j]) and test(s[i + j:]):
				u.append(int(s[:i]) + int(s[i:i + j]) + int(s[i + j:]))
print(max(u))


s = input()
add = []
for i in range(1, len(s) - 1):
	for j in range(i + 1, len(s)):
		a = s[:i]
		b = s[i:j]
		c = s[j:]
		if int(a) <= 1000000 and int(b) <= 1000000 and (int(c) <= 1000000):
			if len(a) > 1 and len(b) > 1 and (len(c) > 1):
				if (len(a) > 1 and int(a) > pow(10, len(a) - 1) - 1) and (len(b) > 1 and int(b) > pow(10, len(b) - 1) - 1) and (len(c) > 1 and int(c) > pow(10, len(c) - 1) - 1):
					add.append(int(a) + int(b) + int(c))
			elif len(a) > 1 and len(b) == 1 and (len(c) == 1):
				if int(a) > pow(10, len(a) - 1) - 1:
					add.append(int(a) + int(b) + int(c))
			elif len(b) > 1 and len(a) == 1 and (len(c) == 1):
				if int(b) > pow(10, len(b) - 1) - 1:
					add.append(int(a) + int(b) + int(c))
			elif len(c) > 1 and len(a) == 1 and (len(b) == 1):
				if int(c) > pow(10, len(c) - 1) - 1:
					add.append(int(a) + int(b) + int(c))
			elif len(a) > 1 and len(b) > 1 and (len(c) == 1):
				if int(a) > pow(10, len(a) - 1) - 1 and int(b) > pow(10, len(b) - 1) - 1:
					add.append(int(a) + int(b) + int(c))
			elif len(b) > 1 and len(c) > 1 and (len(a) == 1):
				if int(b) > pow(10, len(b) - 1) - 1 and int(c) > pow(10, len(c) - 1) - 1:
					add.append(int(a) + int(b) + int(c))
			elif len(c) > 1 and len(a) > 1 and (len(b) == 1):
				if int(c) > pow(10, len(c) - 1) - 1 and int(a) > pow(10, len(a) - 1) - 1:
					add.append(int(a) + int(b) + int(c))
			elif len(a) == 1 and len(b) == 1 and (len(c) == 1):
				add.append(int(a) + int(b) + int(c))
if len(add) == 0:
	print(-1)
else:
	b = sorted(add, reverse=True)
	print(b[0])


s = input()
ans = -1
if len(s) > 21:
	print(-1)
else:
	n = len(s)
	for i in range(1, 8):
		if i >= n:
			break
		m = s[0:i]
		if int(m) > 1000000:
			break
		if m[0] == '0' and i != 1:
			break
		for j in range(1, 8):
			if i + j >= n:
				break
			mm = s[i:i + j]
			if int(mm) > 1000000:
				break
			if mm[0] == '0' and j != 1:
				break
			mmm = s[i + j:]
			if int(mmm) > 1000000:
				continue
			if mmm[0] == '0' and len(mmm) != 1:
				continue
			a = int(m) + int(mm) + int(mmm)
			if a > ans:
				ans = a
	print(ans)


s = input()
lst = [0]
n = len(s)
ans = -1
for c in s:
	lst.append(lst[-1] + int(c))
for i in range(n):
	for j in range(i + 1, n):
		s1 = s[:i]
		s2 = s[i:j]
		s3 = s[j:]
		if len(s1) == 0 or (len(s1) > 1 and s1[0] == '0'):
			continue
		if len(s2) == 0 or (len(s2) > 1 and s2[0] == '0'):
			continue
		if len(s3) == 0 or (len(s3) > 1 and s3[0] == '0'):
			continue
		if int(s1) > 1000000:
			continue
		if int(s2) > 1000000:
			continue
		if int(s3) > 1000000:
			continue
		ans = max(ans, int(s1) + int(s2) + int(s3))
print(ans)


n = input()
l = len(n)
mini = -1
for i in range(1, l - 1):
	for j in range(1, l - 1):
		k = l - i - j
		if k > 0:
			t1 = ''.join(n[:i])
			t2 = ''.join(n[i:i + j])
			t3 = ''.join(n[i + j:])
			if t1[0] == '0' and i > 1 or (t2[0] == '0' and j > 1) or (t3[0] == '0' and k > 1):
				continue
			t1 = int(t1)
			t2 = int(t2)
			t3 = int(t3)
			s = t1 + t2 + t3
			if s > mini and t1 <= 10 ** 6 and (t2 <= 10 ** 6) and (t3 <= 10 ** 6):
				mini = s
print(mini)


s = input()

def f(str):
	if str[0] == '0' and len(str) > 1:
		return -10000000000
	if int(str) > 10 ** 6:
		return -1000000000
	return int(str)
ans = -1
for i in range(1, len(s) - 1):
	for j in range(i + 1, len(s)):
		if f(s[0:i]) >= 0 and f(s[i:j]) >= 0 and (f(s[j:]) >= 0):
			ans = max(ans, f(s[0:i]) + f(s[i:j]) + f(s[j:]))
print(ans)


def max_score(n):
	max_score = 0
	any_choice = False
	for i in range(0, len(n) - 2):
		for j in range(i + 1, len(n) - 1):
			if n[:i + 1][0] == '0' and len(n[:i + 1]) > 1 or (n[i + 1:j + 1][0] == '0' and len(n[i + 1:j + 1]) > 1) or (n[j + 1:][0] == '0' and len(n[j + 1:]) > 1) or (int(n[:i + 1]) > 1000000) or (int(n[i + 1:j + 1]) > 1000000) or (int(n[j + 1:]) > 1000000):
				continue
			else:
				any_choice = True
			new_score = int(n[:i + 1]) + int(n[i + 1:j + 1]) + int(n[j + 1:])
			if new_score > max_score:
				max_score = new_score
	if any_choice:
		return max_score
	else:
		return -1

def main():
	allscores = input()
	print(max_score(allscores))
main()


s = input()
w = len(s)
q = -1
for i in range(w - 2):
	for j in range(i + 1, w - 1):
		(a, b, c) = (s[:i + 1], s[i + 1:j + 1], s[j + 1:])
		if len(a) == len(str(int(a))) and len(b) == len(str(int(b))) and (len(c) == len(str(int(c)))):
			if int(a) <= 10 ** 6 and int(b) <= 10 ** 6 and (int(c) <= 10 ** 6):
				q = max(q, int(a) + int(b) + int(c))
print(q)


s = input()
n = len(s)
max_points = -1
for i in range(1, n - 1):
	for j in range(i + 1, n):
		a = s[:i]
		b = s[i:j]
		c = s[j:]
		if int(a) <= 10 ** 6 and int(b) <= 10 ** 6 and (int(c) <= 10 ** 6):
			if a[0] == '0' and len(a) > 1 or (b[0] == '0' and len(b) > 1) or (c[0] == '0' and len(c) > 1):
				continue
			else:
				points = int(a) + int(b) + int(c)
				if max_points < points:
					max_points = points
print(max_points)


s = input()
ans = -1
for i in range(len(s) - 2):
	for j in range(i + 1, len(s) - 1):
		x = s[:i + 1]
		y = s[i + 1:j + 1]
		z = s[j + 1:]
		if len(x) == len(str(int(x))) and len(y) == len(str(int(y))) and (len(z) == len(str(int(z)))):
			if int(x) <= 1000000.0 and int(y) <= 1000000.0 and (int(z) <= 1000000.0):
				ans = max(ans, int(x) + int(y) + int(z))
print(ans)


s = input()
n = len(s)

def num(x):
	if len(x) > 1 and x[0] == '0':
		return 1000000000
	x = int(x)
	if x > 1000000:
		return 1000000000
	return x
ans = -1
for i in range(1, n - 1):
	for j in range(i + 1, n):
		l = s[:i]
		m = s[i:j]
		r = s[j:]
		cur = num(l) + num(m) + num(r)
		if cur < 100000000:
			ans = max(ans, cur)
print(ans)


a = input()
s = len(a)
ans = -1
if s >= 3:
	for i in range(s - 2):
		for j in range(i + 1, s - 1):
			if i + 1 > 0 + 1 and a[0] == '0' or (j + 1 > i + 2 and a[i + 1] == '0') or (s > j + 2 and a[j + 1] == '0'):
				continue
			if int(a[0:i + 1]) > 1000000 or int(a[i + 1:j + 1]) > 1000000 or int(a[j + 1:s]) > 1000000:
				continue
			ans = max(ans, int(a[0:i + 1]) + int(a[i + 1:j + 1]) + int(a[j + 1:s]))
print(ans)


s = input()
n = len(s)
maxi = -1
for i in range(n - 2):
	for j in range(i + 1, n - 1):
		(a, b, c) = (s[:i + 1], s[i + 1:j + 1], s[j + 1:])
		if len(a) == len(str(int(a))) and len(b) == len(str(int(b))) and (len(c) == len(str(int(c)))):
			if int(a) <= 1000000.0 and int(b) <= 1000000.0 and (int(c) <= 1000000.0):
				maxi = max(maxi, int(a) + int(b) + int(c))
print(maxi)


s = input()
n = len(s)
ans = -1

def f(x):
	if x[0] == '0' and len(x) > 1:
		return -1000000000000000000000000000000000000000000000000
	ret = int(x)
	if ret > 1000000:
		return -1000000000000000000000000000000000000000000000000
	return ret
for i in range(1, n):
	for j in range(i + 1, n):
		ans = max(ans, f(s[0:i]) + f(s[i:j]) + f(s[j:]))
print(ans)


a = input()
n = len(a)
fl = 1
temp = 0
for x in range(n - 1):
	x += 1
	for y in range(n - 1 - x):
		y += x + 1
		if len(a[:x]) > 1 and a[:x][0] == '0':
			continue
		a1 = int(a[:x])
		if a1 > 1000000:
			continue
		if len(a[x:y]) > 1 and a[x:y][0] == '0':
			continue
		b1 = int(a[x:y])
		if b1 > 1000000:
			continue
		if len(a[y:]) > 1 and a[y:][0] == '0':
			continue
		c1 = int(a[y:])
		if c1 > 1000000:
			continue
		su = a1 + b1 + c1
		fl = 0
		temp = max(su, temp)
if fl:
	print('-1')
else:
	print(temp)


s = input()
a = -1
for i in range(1, len(s)):
	for j in range(i + 1, len(s)):
		x = [s[:i], s[i:j], s[j:]]
		if sum(map(lambda s: (len(s) < 2 or s[0] != '0') and int(s) <= 10 ** 6, [s[:i], s[i:j], s[j:]])) == 3:
			a = max(a, sum(map(int, x)))
print(a)


s = input().strip()
n = len(s)
big = 10 ** 6
result = -1
for i in range(1, n):
	if s[0] == '0' and i > 1:
		break
	a = int(s[:i])
	if a > big:
		break
	for j in range(i + 1, n):
		if s[i] == '0' and j - i > 1:
			break
		b = int(s[i:j])
		if b > big:
			break
		if s[j] == '0' and n - j > 1:
			continue
		c = int(s[j:])
		if c > big:
			continue
		result = max(result, a + b + c)
print(result)


A = input()
M = 10 ** 6
best = -1
for i in range(1, len(A)):
	for j in range(i + 1, len(A)):
		if (A[:i] == '0' or A[0] != '0') and (A[i:j] == '0' or A[i] != '0') and (A[j:] == '0' or A[j] != '0') and (int(A[:i]) <= M) and (int(A[i:j]) <= M) and (int(A[j:]) <= M):
			best = max([best, int(A[:i]) + int(A[i:j]) + int(A[j:])])
print(best)


def main():
	s = input()
	n = len(s)
	ans = -1
	for i in range(1, n):
		i1 = int(s[0:i])
		if i1 > 1000000:
			continue
		if str(i1) != s[0:i]:
			continue
		for j in range(i + 1, n):
			j1 = int(s[i:j])
			k1 = int(s[j:])
			if str(j1) != s[i:j] or str(k1) != s[j:]:
				continue
			if j1 > 1000000 or k1 > 1000000:
				continue
			ans = max(ans, i1 + j1 + k1)
	print(ans)
main()


def isint(strx):
	if strx == '0':
		return True
	if strx[0] == '0':
		return False
	return int(strx) <= 1000000
maxx = -1
x = input()
for i in range(1, len(x)):
	for j in range(i + 1, len(x)):
		(a, b, c) = (x[:i], x[i:j], x[j:])
		if isint(a) and isint(b) and isint(c):
			maxx = max(maxx, int(a) + int(b) + int(c))
print(maxx)