Công ty xây dựng FB vừa ký hợp đồng sửa chữa tuyến đường đi qua trung tâm thành phố. Trên tuyến đường này có nhiều hạng mục cần thi công, mỗi hạng mục cần số ngày hoàn thành khác nhau. Công ty có 2 đội công nhân có năng lực làm việc như nhau. Đội 1 sẽ thi công từ đầu tuyến đường, đội 2 sẽ thi công từ cuối tuyến đường ngược trở về. Mỗi hạng mục chỉ do duy nhất một đội thi công. Hãy giúp công ty tính toán thời gian hoàn thành sửa chữa cả tuyến đường. Cho một ký tự, chỉ gồm các ký tự in thường từ a đến z, và các chữ số từ 0 đến 9, mỗi ký tự hoặc chữ số đại diện cho một hạng mục cần thi công. Mỗi ký tự cho biết hạng mục chỉ cần thời gian hoàn thành là một ngày, mỗi chữ số cho biết số ngày hoàn thành của hạng mục đó, chẳng hạn chữ số 5 là cần làm trong 5 ngày.

Input

• Một dòng ghi xâu S, độ dài ~<=10^5~.

Output

• Ghi một số nguyên cho biết số ngày ít nhất để hoàn thành sửa chữa cả tuyến đường.

Sample input

abbc4c

Sample output

5

Giải thích

• Đội 1 hoàn thành các hạng mục a,b,b,c mất 4 ngày
• Đội 2 hoàn thành các hạng mục 4 và c, mất 5 ngày