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.

Input

• Một dòng chứa xâu \(S\) không quá \(10^5\) 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.

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.

Example

abbc4c

5