Luck is in Numbers

题目描述

Vasya has been collecting transport tickets for quite a while now. His collection contains several thousands of tram, trolleybus and bus tickets. Vasya is already fed up with the traditional definition of what a lucky ticket is. Thus, he's looking for new perspectives on that. Besides, Vasya cannot understand why all tickets are only divided into lucky and unlucky ones. He thinks that all tickets are lucky but in different degrees. Having given the matter some thought, Vasya worked out the definition of a ticket's degree of luckiness. Let a ticket consist of $ 2n $ digits. Let's regard each digit as written as is shown on the picture: You have seen such digits on electronic clocks: seven segments are used to show digits. Each segment can either be colored or not. The colored segments form a digit. Vasya regards the digits as written in this very way and takes the right half of the ticket and puts it one the left one, so that the first digit coincides with the $ n+1 $ -th one, the second digit coincides with the $ n+2 $ -th one, ..., the $ n $ -th digit coincides with the $ 2n $ -th one. For each pair of digits, put one on another, he counts the number of segments colored in both digits and summarizes the resulting numbers. The resulting value is called the degree of luckiness of a ticket. For example, the degree of luckiness of ticket 03 equals four and the degree of luckiness of ticket 2345 equals six. You are given the number of a ticket containing $ 2n $ digits. Your task is to find among the tickets whose number exceeds the number of this ticket but also consists of $ 2n $ digits such ticket, whose degree of luckiness exceeds the degrees of luckiness of the given ticket. Moreover, if there are several such tickets, you should only choose the one with the smallest number.

输入输出格式

输入格式

The first line contains the number of the ticket that consists of $ k $ characters ( $ k=2n,1<=n<=10^{5} $ ).

输出格式

Print the number of the sought ticket or "-1" (without the quotes) if no such ticket exists.

输入输出样例

输入样例 #1

13

输出样例 #1

20

输入样例 #2

2345

输出样例 #2

2348

输入样例 #3

88

输出样例 #3

-1