CodeForces - 95B

Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

One day Petya came across a positive integer n. Help him to find the least super lucky number which is not less than n.

Input

The only line contains a positive integer n (1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰). This number doesn't have leading zeroes.

Output

Output the least super lucky number that is more than or equal to n.

Examples

Input

4500

Output

4747

Input

47

Output

47

题目大意：输入一个正整数，求不小与这个数的最小的超级幸运数（超级幸运数是4和7的个数相同的数，并且只有4和7）
思路：这道题dfs能过真是吓到我了，数据这么大，这也能过只能说数据有点水，思路看代码吧

#include<iostream>
#include<string.h>
#include<map>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<set>
#include<queue>
typedef long long ll;
using namespace std;
const ll mod=1e9+7;
const int maxn=1e6+10;
const int maxk=5e3+10;
const int maxx=1e4+10;
const ll maxe=1000+10;
#define INF 0x3f3f3f3f3f3f
#define Lson l,mid,rt<<1
#define Rson mid+1,r,rt<<1|1
char a[maxn],ans[maxn];
int len;
bool dfs(int pol,int sum1,int sum2,bool limit)//当前位，4的个数，7的个数，是否已经没有限制了
{
    if(pol>=len) return true;
    if(limit)//没有限制了，那么直接把剩余的4和7放进去就可以了
    {
        for(int i=0;i<sum1;i++) ans[pol++]='4';
        for(int i=0;i<sum2;i++) ans[pol++]='7';
        return true;
    }
    if(sum1&&a[pol]<='4')
    {
        if(dfs(pol+1,sum1-1,sum2,a[pol]!='4'))
        {
            ans[pol]='4';
            return true;
        }
    }
    if(sum2&&a[pol]<='7')
    {
        if(dfs(pol+1,sum1,sum2-1,a[pol]!='7'))
        {
            ans[pol]='7';
            return true;
        }
    }
    return false;//4和7都不能选，那么代表要加两位数了
}
int main()
{
    cin>>a;
    len=strlen(a);
    if(len&1||!dfs(0,len/2,len/2,0))//如果长度是奇数的话直接加一位数，前面的是4后面的是7，判断偶数的时候是否有满足条件的数
    {
        if(len&1) len++;
        else len+=2;
        int i;
        for(i=0;i<len/2;i++) ans[i]='4';
        for(i;i<len;i++) ans[i]='7';
    }
    cout<<ans<<endl;
    return 0;
}