class-homework

Ramesh and Suresh were in the same class and got home work from their mathematics teacher. The Homework consists of N strings and each string consists of only digits. The task which they need to perform is that they need to divide the string into 4 integers such that their sum is maximum.

Note:

Each integer should be ≤ 10^12 and should not contain any leading zeroes.

As we know that Suresh and Ramesh are weak in mathematics and also they don't want to be punished. So, they need your help for finding the answer.
INPUT:
First line contains an integer N denoting the number of strings. Next N lines contain N strings each consists of digits only.
OUTPUT:
For each test case, Print the required answer if exists. Print "unlucky" otherwise.

CONSTRAINTS:

1 ≤ N ≤ 10^4
1 ≤ size of each string ≤ 20

SUBTASKS:

subtask 1 : 1 ≤ N ≤ 10^2 : ( 50 pts )
subtask 2 : 1 ≤ N ≤ 10^4 : ( 50 pts )

SAMPLE INPUT
3
4251
52310
00006

SAMPLE OUTPUT
12
56
unlucky

Explanation

In test case 1: 4 integers are 4,2,5,1. So maximum sum is 12.
In test case 2: 4 integers are 52,3,1,0. So maximum sum is 56.
In test case 3: None of division (0 , 0 , 0 , 06) , (0 , 00 , 0 , 6 ) is valid.

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Ad-hoc


Solutions:
T=eval(input())
best=-1
bound=10**12
boundS=str(bound)
def findBest(s,off,n,sofar):
	#print "looking for best fo",s[off:],n
	remain=len(s)-off
	if remain<n: return
	global best
	if n==1:
		if remain>13:
			return
		if s[off]=="0":
			if len(s)-off>1: return
		if remain==13 and s[off:]!=boundS:
			return
		
		val=sofar+int(s[off:])
		#print "found",val
		if val>best:
			best=val
		return	
	if s[off]=="0":
		findBest(s,off+1,n-1,sofar)
		return
	for i in range(1,min(13,remain-n+2)):
		findBest(s,off+i,n-1,sofar+int(s[off:off+i]))
	if remain-n+1>=13:
		if s[off:off+13]==boundS:
			findBest(s,off+13,n-1,sofar+bound)
for _ in range(T):
	best=-1
	s=input()
	findBest(s,0,4,0)
	if best>=0: print(best)
	else: print("unlucky")