stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstdio>

using namespace std;



typedef long long ll;



ll a[100010];

int main()

{

    int x, n;

    while(scanf("%d%d", &n, &x) != EOF)

    {

        ll sum = 0;

        for(int i = 0; i < n; i++)

        {

            scanf("%lld", &a[i]);

            if(a[i] > x)

                {

                    sum += a[i] - x;

                    a[i] = x;

                }

        }

        for(int i = 1; i < n; i++)

        {

            if(a[i] + a[i - 1] > x)

            {

                sum += a[i] - (x - a[i - 1]);

                a[i] = x - a[i - 1];

            }

        }

        printf("%lld\n", sum);

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.179812237222822x):
#include<stdio.h>

int main()

{

	int n,x;

	scanf("%d%d",&n,&x);

	long long a,b,ans=0;

	scanf("%lld",&a);

	if(a>x){

		ans+=a-x;

		a=x;

	}

	for(int i=1;i<n;i++)

	{

		scanf("%lld",&b);

		if((a+b)>x)

		{

			ans+=a+b-x;

			a=x-a;

		}

		else a=b;

	}

	printf("%lld\n",ans);

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <functional>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <bitset>

#include <cassert>

#include <exception>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<string,ll> P;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

typedef vector<P> vp;

#define rep(i,a,n) for(ll i = (a);i < (n);i++)

#define per(i,a,n) for(ll i = (a);i > (n);i--)

#define lep(i,a,n) for(ll i = (a);i <= (n);i++)

#define pel(i,a,n) for(ll i = (a);i >= (n);i--)

#define clr(a,b) memset((a),(b),sizeof(a))

#define pb push_back

#define mp make_pair

#define all(c) (c).begin(),(c).end()

#define sz size()

#define print(X) cout << (X) << endl

const ll INF = 1e+9+7;

ll n,m,l,ans;

string s,t;

ll d[200010],dp[500][500];



int main(){

  cin >> n >> m;

  clr(d,0);

  rep(i,0,n)cin >> d[i];

  rep(i,0,n){

    l = 0;

    if(d[i] > m){

      l = d[i] - m;

      d[i] = m;

    }

    if(d[i] + d[i+1] > m){

      ll p = d[i] + d[i+1] - m;

      d[i+1] -= p;

      l += p;

    }

    ans += l;

  }

  print(ans);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.605320420869851x):
#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <functional>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> P;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<char> vc;

typedef vector<string> vs;

typedef vector<P> vp;

#define rep(i,a,n) for(ll i = (a);i < (n);i++)

#define per(i,a,n) for(ll i = (a);i > (n);i--)

#define lep(i,a,n) for(ll i = (a);i <= (n);i++)

#define pel(i,a,n) for(ll i = (a);i >= (n);i--)

#define clr(a,b) memset((a),(b),sizeof(a))

#define pb push_back

#define all(c) (c).begin(),(c).end()

#define sz size()

#define endl "\n"

#define print(X) cout << (X) << "\n"

// // #define input(X) getline(cin,X)

static const int INF = 1e+9+7;

static const ll INFL = 1e+18+7;

ll n,m,l;

string s,t;

ll d[200010],e[200010],dp[1001][1001];

char field[200][200];



int main(){

  ll ans = 0;

  cin >> n >> m;

  rep(i,0,n)cin >> d[i];

  rep(i,0,n){

    ll ans1 = 0, ans2 = 0;

    if(d[i] > m){

      ans1 = d[i] - m;

      d[i] -= ans1;

    }

    if(d[i]+d[i+1] > m){

      ans2 = d[i] + d[i+1] - m;

      d[i+1] -= ans2;

    }

    ans += ans1 + ans2;

  }

  print(ans);

  return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;

int main(){

  int n,x;

  cin>>n>>x;

  int a[114514]={};

  for(int i=0;i<n;i++){

    cin>>a[i];

  }

  long long int ans=0;

  for(int i=1;i<n;i++){

    if(a[i]+a[i-1]>x){

		ans+=a[i]+a[i-1]-x;

      	a[i]=x-a[i-1];

      	if(a[i]<0){

			a[i-1]=-a[i];

          a[i]=0;

          ans+=-a[i];

        }

    }

  }

  cout<<ans<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.4363975517835856x):
#include<bits/stdc++.h>

#define all(vec) vec.begin(),vec.end()

using namespace std;

typedef long long int ll;

typedef pair<int,int> P;

const ll MOD=1000000007;

const ll INF=1000000010;

const ll LINF=4000000000000000010LL;

const int MAX=310;

const double EPS=1e-9;

int dx[4]={0,1,0,-1};

int dy[4]={1,0,-1,0};

int main(){

	ll n,x;cin>>n>>x;

	ll a[100010];

	for(int i=0;i<n;i++){

		cin>>a[i];

	}

	ll ans=0;

	if(a[0]>x){

		ans+=a[0]-x;

		a[0]=x;

	}

	for(int i=1;i<n;i++){

		if(a[i-1]+a[i]>x){

			ans+=a[i-1]+a[i]-x;

			a[i]-=a[i-1]+a[i]-x;

		}

	}

	cout<<ans<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



const int N = 2e5+5;



int main()

{

	long long n, d, a;

	long long ans = 0, cur = 0;

	vector<pair<long long, long long>> monsters(N);

	queue<pair<long long,long long>> q; //dist , contribution to cur

	cin >> n >> d >> a;

	d *= 2;

	for(int i = 0; i < n; ++i)

		cin >> monsters[i].first >> monsters[i].second;

	sort(monsters.begin(), monsters.begin()+n);



	for(int i = 0; i < n; ++i){

		while(!q.empty()){

			if(q.front().first < monsters[i].first){

				cur -= q.front().second;

				q.pop();

			}

			else

				break;

		}

		monsters[i].second -= (cur*a);

		if(monsters[i].second > 0){

			long long contrib = ((monsters[i].second + a - 1) / a);

			ans += contrib;

			cur += contrib;

			q.push({monsters[i].first+d, contrib});

		}

	}

	cout << ans;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.200374907288443x):
#include<bits/stdc++.h>

using namespace std;

long long sum[200000];

int main()

{

	long long n,d,damage;

	cin>>n>>d>>damage;

	std::vector<pair<long long,long long> > v;

	for (long long i = 0; i < n; ++i)

	{

		long long x,h;

		cin>>x>>h;

		v.push_back(make_pair(x,h));

	}

	sort(v.begin(),v.end());

	long long ans = 0;

	for (long long i = 0; i < n; ++i)

	{



		if(i!=0)

			sum[i] += sum[i-1];

		v[i].second = v[i].second-sum[i];

		// printf("%lld -> %lld\n",i,sum[i] );

		if(v[i].second <= 0)

			continue;

		long long l = i, r = n;

		while(l<=r)

		{

			long long m = (l+r)/2;

			// printf("-=--=%lld %lld %lld\n",l,r,m );

			if(v[m].first>v[i].first+2*d)

			{

				// printf("nn\n");

				r = m - 1;

			}

			else

			{

				// printf("op\n");

				l = m + 1;

			}

		}

		// printf("l is %lld for i %lld\n",l,i );

		long long c = 0;

		c = v[i].second/damage;

		if(v[i].second%damage>0)

			c++;

		ans += c;

		long long impact = damage*c;

		// printf("impact %lld\n",impact );

		sum[i] += impact;

		sum[l] -= impact;

		// printf("sum %lld %lld\n",i,sum[i] );

	}

	cout<<ans<<endl;



	

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define st first

#define nd second

using namespace std;

using pii = pair<int,int>;

int bz = 2e5;

pii p[(int)2e5 + 10];

long long bit[(int)2e5 + 10];

void update(int pos, long long val){

    for(;pos <= bz; pos += pos & -pos){

        bit[pos]+=val;

    }

    return;

}

long long query(int pos){

    long long sum = 0LL;

    for(;pos > 0;pos-=pos&-pos){

        sum+=bit[pos];

    }

    return sum;

}

int main(){

    int n,d,a;

    scanf("%d%d%d",&n,&d,&a);

    bz = n;

    for(int i =1;i<=n;i++){

        scanf("%d%d",&p[i].st,&p[i].nd);

    }

    sort(p+1,p+n+1);

    int ti = 0,to = -1,it = 1;

    long long ans = 0LL;

    p[0] ={0,0};

    for(int i =1;i<=n;i++){

        update(i, 1LL *( p[i].nd - p[i-1].nd));

        long long x = query(i);

        if(x <= 0LL) continue;

        int dis = p[i].st + 2 * d;

        for(it = max(it,i);it <= n && p[it].st <= dis;it++);

        ti = x/a + (x % a > 0);

        update(i,1LL * -1 * ti * a);

        if(it <= n) update(it,1LL * ti * a);

        ans += 1LL * ti;

    }

    printf("%lld",ans);



}


// Faster C++ solution for the same problem (measured speedup: 5.180901282056809x):
#include<cstdio>

#include<algorithm>

#define st first

#define nd second



using namespace std;

using pii = pair<int, int>;

const int N = 2e5 + 10;

int prefixArray[N];

pii mons[N];



int main(){

    int n, d, a;

    scanf("%d %d %d", &n, &d, &a);

    for(int i = 1; i <= n; i++){

        scanf("%d %d", &mons[i].st, &mons[i].nd);

    }

    sort(mons + 1, mons + n + 1);

    int ptr = 1;

    long long ans = 0LL;

    for(int i = 1; i <= n; i++){

        while(ptr <= n && mons[ptr].st <= mons[i].st + 2 * d)

            ptr++;

        prefixArray[i] += prefixArray[i - 1];

        if(prefixArray[i] >= mons[i].nd)

            continue;

        int bombTime = (mons[i].nd - prefixArray[i] + a - 1) / a;

        ans += 1LL * bombTime;

        prefixArray[i] += bombTime * a;

        prefixArray[ptr] -= bombTime * a;

    }

    printf("%lld", ans);





}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)

//long long mo = 1e9 + 7;

typedef long long ll;



int main(){

    ll N,D,A;

    cin >> N >> D >> A;

    vector<pair<ll,ll>> X(N);

    vector<ll> L(200100);

    rep(i,N){

        cin >> X[i].first >> X[i].second;

    }

    sort(X.begin(), X.end());

    ll cnt = 0;

    D *= 2;

    queue<pair<ll,ll>> que;

    ll total = 0;

    for(int i=0;i<N;i++){

        while(!que.empty() && que.front().first < X[i].first){

            total -= que.front().second;

            que.pop();

        }

        if(X[i].second > total){

            ll damage = X[i].second - total;

            ll num = (damage + A - 1) / A;

            cnt += num;

            total += num*A;

            que.push(make_pair(X[i].first + D, num*A));

        }

    }





    cout << cnt  << endl;

}


// Faster C++ solution for the same problem (measured speedup: 2.599450987675218x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)

#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)

long long mo = 1e9 + 7;

typedef long long ll;

typedef long double ld;

typedef pair<int,int> Pii;

typedef pair<ll,ll> Pll;

template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }

template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}

ld PI=3.14159265358979323846;



int main(){

    ll N,D,A;

    cin >> N >> D >> A;

    vector<Pll> P(N);

    rep(i,N){

        cin >> P[i].first >> P[i].second;

    }

    sort(P.begin(), P.end());

    queue<Pll> que;

    ll Ac = 0;

    ll ans = 0;

    rep(i,N){

        ll X = P[i].first;

        ll H = P[i].second;

        while(!que.empty() && X >= que.front().first){

            Ac -= A*que.front().second;

            que.pop();

        }

        if(H > Ac){

            ll n = ((H-Ac)+A-1)/A;

            que.push(Pll(X+2*D+1, n));

            Ac += A*n;

            ans += n;

        }else{

            continue;

        }

    }

    cout << ans << endl;

}
// Slower C++ solution:
#include <cstdio>

#include <algorithm>

#include <utility>



#include <cstdio>



template<typename T, size_t MAX_N>

class BIT

{

	public:

		BIT(size_t n) : _bit(), _n(n) {}



		T sum(size_t i)

		{

			T r = 0;

			while (i > 0)

			{

				r += _bit[i];

				i &= (i - 1);

			}

			return r;

		}



		void add(size_t i, T x)

		{

			while (i <= _n)

			{

				_bit[i] += x;

				i += i & -i;

			}

		}



	protected:

		T _bit[MAX_N + 1];

		size_t _n;

};



int main()

{

	int n;

	long long d, a;

	scanf("%d%lld%lld", &n, &d, &a);

	using pair = std::pair<long long, long long>;

	pair enemy[200000];

	for (int i = 0; i < n; ++i)

	{

		long long x, h;

		scanf("%lld%lld", &x, &h);

		enemy[i].first = x;

		enemy[i].second = h;

	}

	std::sort(enemy, enemy + n);

	BIT<long long, 200000> bit0(n);

	BIT<long long, 200000> bit1(n);

	auto pquery = [&](int x)

	{

		return (bit1.sum(x) * x + bit0.sum(x)) - (bit1.sum(x - 1) * (x - 1) + bit0.sum(x - 1));

	};

	long long ans = 0;

	for (int i = 0; i < n; ++i)

	{

		long long left = enemy[i].second - pquery(i + 1);

		if (left <= 0) continue;

		long long l = enemy[i].first;

		long long r = l + 2 * d;

		int ub = std::upper_bound(enemy, enemy + n, pair{r, 0}, [](auto& a, auto& b){ return a.first < b.first; }) - enemy;

		long long times = (left + a - 1) / a;

		ans += times;

		long long bomb = times * a;

		bit0.add(i + 1, -bomb * i);

		bit1.add(i + 1, bomb);

		bit0.add(ub + 1, bomb * ub);

		bit1.add(ub + 1, -bomb);

	}

	printf("%lld\n", ans);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3334249385929904x):
#include <cstdio>

#include <algorithm>

#include <utility>



template<typename T, size_t MAX_N>

class BIT

{

	public:

		BIT(size_t n) : _bit(), _n(n) {}



		T sum(size_t i)

		{

			T r = 0;

			while (i > 0)

			{

				r += _bit[i];

				i &= (i - 1);

			}

			return r;

		}



		void add(size_t i, T x)

		{

			while (i <= _n)

			{

				_bit[i] += x;

				i += i & -i;

			}

		}



	protected:

		T _bit[MAX_N + 1];

		size_t _n;

};



int main()

{

	int n;

	long long d, a;

	scanf("%d%lld%lld", &n, &d, &a);

	using pair = std::pair<long long, long long>;

	pair enemy[200000];

	for (int i = 0; i < n; ++i)

	{

		long long x, h;

		scanf("%lld%lld", &x, &h);

		enemy[i].first = x;

		enemy[i].second = h;

	}

	std::sort(enemy, enemy + n);

	BIT<long long, 200000> bit(n);

	long long ans = 0;

	for (int i = 0; i < n; ++i)

	{

		long long left = enemy[i].second - bit.sum(i + 1);

		if (left <= 0) continue;

		long long l = enemy[i].first;

		long long r = l + 2 * d;

		int ub = std::upper_bound(enemy, enemy + n, pair{r, 0}, [](auto& a, auto& b){ return a.first < b.first; }) - enemy;

		long long times = (left + a - 1) / a;

		ans += times;

		long long bomb = times * a;

		bit.add(i + 1, bomb);

		bit.add(ub + 1, -bomb);

	}

	printf("%lld\n", ans);

	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>



using namespace std;



typedef long long ll;



const ll INF=0x3fffffffffffffffll;



/*

11111

= 99999 / 9

= (10 ^ 6 - 1) / 9



(10 ^ n - 1) / 9



*/



ll n;



inline ll get_phi(ll x)

{

    ll res=x;

    for(int i=2;i<=x/i;i++)

        if(x%i==0)

        {

            res-=res/i;

            while(x%i==0)x/=i;

        }

    if(x>1)res-=res/x;

    return res;

}



ll qmi(ll k,ll mod)

{

    ll res=1,a=10;

    while(k)

    {

        if(k&1)res=res*a%mod;

        a=a*a%mod;

        k>>=1;

    }

    return res%mod;

}



int main()

{

    scanf("%lld",&n);

    if(n&1)

    {

        if(n%7==0)n/=7;

        n*=9;

        ll phi=get_phi(n),res=INF;

        for(ll i=1;i<=phi/i;i++)

            if(phi%i==0)

            {

                if(qmi(i,n)==1)res=min(res,i);

                else if(qmi(phi/i,n)==1)res=min(res,phi/i);

            }

        printf("%lld\n",res==INF?-1:res);

    }

    else puts("-1");

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.7259142781596974x):
#include <cstdio>

#include <cstring>



using namespace std;



typedef long long ll;



const ll INF=0x3fffffffffffffffll;



ll n;



inline ll min(ll a,ll b){return a<b?a:b;}



inline ll get_phi(ll x)

{

    ll res=x;

    for(int i=2;i<=x/i;i++)

        if(x%i==0)

        {

            res-=res/i;

            while(x%i==0)x/=i;

        }

    if(x>1)res-=res/x;

    return res;

}



ll qmi(ll k,ll mod)

{

    ll res=1,a=10;

    while(k)

    {

        if(k&1)res=res*a%mod;

        a=a*a%mod;

        k>>=1;

    }

    return res%mod;

}



int main()

{

    scanf("%lld",&n);

    if(n%10)

    {

        if(n%7==0)n/=7;

        n*=9;

        ll phi=get_phi(n),res=INF;

        for(ll i=1;i<=phi/i;i++)

            if(phi%i==0)

            {

                if(qmi(i,n)==1)res=min(res,i);

                else if(qmi(phi/i,n)==1)res=min(res,phi/i);

            }

        printf("%lld\n",res==INF?-1:res);

    }

    else puts("-1");

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>



using namespace std;



typedef long long ll;



const ll INF=0x3fffffffffffffffll;



/*

11111

= 99999 / 9

= (10 ^ 6 - 1) / 9



(10 ^ n - 1) / 9



*/



ll n;



inline ll get_phi(ll x)

{

    ll res=x;

    for(int i=2;i<=x/i;i++)

        if(x%i==0)

        {

            res-=res/i;

            while(x%i==0)x/=i;

        }

    if(x>1)res-=res/x;

    return res;

}



ll qmi(ll k,ll mod)

{

    ll res=1,a=10;

    while(k)

    {

        if(k&1)res=res*a%mod;

        a=a*a%mod;

        k>>=1;

    }

    return res%mod;

}



int main()

{

    scanf("%lld",&n);

    if(n&1)

    {

        if(n%7==0)n/=7;

        n*=9;

        ll phi=get_phi(n),res=INF;

        for(ll i=1;i<=phi/i;i++)

            if(phi%i==0)

            {

                if(qmi(i,n)==1)res=min(res,i);

                else if(qmi(phi/i,n)==1)res=min(res,phi/i);

            }

        printf("%lld\n",res==INF?-1:res);

    }

    else puts("-1");

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.746501960085045x):
#include <cstdio>

#include <cstring>



using namespace std;



typedef long long ll;



const ll INF=0x3fffffffffffffffll;



ll n;



inline ll min(ll a,ll b){return a<b?a:b;}



inline ll get_phi(ll x)

{

    ll res=x;

    for(int i=2;i<=x/i;i++)

        if(x%i==0)

        {

            res-=res/i;

            while(x%i==0)x/=i;

        }

    if(x>1)res-=res/x;

    return res;

}



ll qmi(ll k,ll mod)

{

    ll res=1,a=10;

    while(k)

    {

        if(k&1)res=res*a%mod;

        a=a*a%mod;

        k>>=1;

    }

    return res%mod;

}



int main()

{

    scanf("%lld",&n);

    if(n%2&&n%5)

    {

        if(n%7==0)n/=7;

        n*=9;

        ll phi=get_phi(n),res=INF;

        for(ll i=1;i<=phi/i;i++)

            if(phi%i==0)

            {

                if(qmi(i,n)==1)res=min(res,i);

                else if(qmi(phi/i,n)==1)res=min(res,phi/i);

            }

        printf("%lld\n",res);

    }

    else puts("-1");

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>



using namespace std;



typedef long long ll;



const ll INF=0x3fffffffffffffffll;



/*

11111

= 99999 / 9

= (10 ^ 6 - 1) / 9



(10 ^ n - 1) / 9



*/



ll n;



inline ll get_phi(ll x)

{

    ll res=x;

    for(int i=2;i<=x/i;i++)

        if(x%i==0)

        {

            res-=res/i;

            while(x%i==0)x/=i;

        }

    if(x>1)res-=res/x;

    return res;

}



ll qmi(ll k,ll mod)

{

    ll res=1,a=10;

    while(k)

    {

        if(k&1)res=res*a%mod;

        a=a*a%mod;

        k>>=1;

    }

    return res%mod;

}



int main()

{

    scanf("%lld",&n);

    if(n&1)

    {

        if(n%7==0)n/=7;

        n*=9;

        ll phi=get_phi(n),res=INF;

        for(ll i=1;i<=phi/i;i++)

            if(phi%i==0)

            {

                if(qmi(i,n)==1)res=min(res,i);

                else if(qmi(phi/i,n)==1)res=min(res,phi/i);

            }

        printf("%lld\n",res==INF?-1:res);

    }

    else puts("-1");

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.57623184834715x):
#include <cstdio>



int main()

{

    int k;

    scanf("%d", &k);

    for (int i = 1, p = 7; i < 9 * k; i ++ , p = (10 * p + 7) % k)

        if (p % k == 0)

        {

            printf("%d\n", i);

            return 0;

        }

    puts("-1");

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>



using namespace std;



typedef long long ll;



const ll INF=0x3fffffffffffffffll;



/*

11111

= 99999 / 9

= (10 ^ 6 - 1) / 9



(10 ^ n - 1) / 9



*/



ll n;



inline ll get_phi(ll x)

{

    ll res=x;

    for(int i=2;i<=x/i;i++)

        if(x%i==0)

        {

            res-=res/i;

            while(x%i==0)x/=i;

        }

    if(x>1)res-=res/x;

    return res;

}



ll qmi(ll k,ll mod)

{

    ll res=1,a=10;

    while(k)

    {

        if(k&1)res=res*a%mod;

        a=a*a%mod;

        k>>=1;

    }

    return res%mod;

}



int main()

{

    scanf("%lld",&n);

    if(n&1)

    {

        if(n%7==0)n/=7;

        n*=9;

        ll phi=get_phi(n),res=INF;

        for(ll i=1;i<=phi/i;i++)

            if(phi%i==0)

            {

                if(qmi(i,n)==1)res=min(res,i);

                else if(qmi(phi/i,n)==1)res=min(res,phi/i);

            }

        printf("%lld\n",res==INF?-1:res);

    }

    else puts("-1");

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.738964905770642x):
#include <cstdio>



typedef long long ll;



const int INF=0x3fffffff;



ll n;



int min(int a, int b)

{

    return a < b ? a : b;

}



// 欧拉函数的板子，返回 phi(x)

int get_phi(int x)

{

    int res = x;

    for (int i = 2; i <= x / i; i ++ )

        if (x % i == 0)

        {

            res -= res / i;

            while (x % i == 0) x /= i;

        }

    if (x > 1) res -= res / x;

    return res;

}



// 快速幂板子，求 10 的 k 次方模 mod 的结果

int qmi(int k, int mod)

{

    int res = 1, a = 10;

    while (k)

    {

        // mod 即 c，最大是 n * 9 = 9e6，乘法就可能会爆 int，要转 long long 

        if (k & 1) res = res * 1ll * a % mod;

        a = a * 1ll * a % mod;

        k >>= 1;

    }

    return res;

}



int main()

{

    scanf("%d", &n);

    // 让 n 变成 c

    if (n % 7 == 0) n /= 7; // 由于 7 是质数，所以这里不用再求一遍最大公约数，直接判断是否有因子 7 即可

    n *= 9;

    // phi 存 phi(c) 的值。res 记录答案，初始化为正无穷

    int phi = get_phi(n), res = INF;

    for (int i = 1; i <= phi / i; i ++ )

        if (phi % i == 0) // 如果 i 是 phi 的因子，那么分别判断 i 和 phi / i 是否是合法解，如果是，则更新答案

            if (qmi(i, n) == 1) res = min(res, i); // 由于 i <= phi / i，所以如果 i 是合法解，就不用再判断 phi / i 了

            else if (qmi(phi / i, n) == 1) res = min(res, phi / i);

    printf("%d\n", res == INF ? -1 : res); // 如果 res == INF，说明无解，输出 -1，否则输出 res

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define int long long

using namespace std;



int n,ii=0,now=0;



signed main()

{

	cin>>n;

	while (ii<=80000000)

	{

		ii++;

		now=(now*10+7)%n;

		

		if (now==0)  return cout<<ii<<endl,0;

	}

	cout<<-1<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.00929438820963x):
#include <cstdio>

int k,ans=1;

int main(){

    scanf("%d",&k);

    for(int n=7;n%k;n=(n*10ll+7ll)%k,ans++) if(ans>=k){puts("-1");return 0;}

    printf("%d\n",ans);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int a, b, c, m;

int main() {

	cin >> a >> b >> c >> m;

	int maxi=0;

	maxi=max(a, max(b, c));

	if(maxi==a){

	    while(m--) a*=2;

	    cout << a+b+c << endl;

	}

	else if(maxi==b) {

	    while(m--) b*=2;

	    cout << a+b+c << endl;

	}

	else {

	    while(m--) c*=2;

	    cout << a+b+c << endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.245191467110137x):
#include<stdio.h>

#include<string.h>

#include<ctype.h>



int main(){

	int a, b, c;

	int k;

	scanf("%d %d %d", &a, &b, &c);

	scanf("%d", &k);

	if(a>b && a>c) printf("%d\n", (a<<k)+b+c);

	else if(b>a && b>c) printf("%d\n", a+(b<<k)+c);

	else printf("%d\n", a+b+(c<<k));

	return 0;

}
// Slower C++ solution:
//xahid f

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int val[3],k;

    cin>>val[0]>>val[1]>>val[2]>>k;

    sort(val,val+3);

    cout<<val[0]+val[1]+val[2]*pow(2,k)<<endl;

    

}

// Faster C++ solution for the same problem (measured speedup: 5.316813523940272x):
#include<stdio.h>

#include<string.h>

#include<ctype.h>



int main(){

	int a, b, c;

	int k;

	scanf("%d %d %d", &a, &b, &c);

	scanf("%d", &k);

	if(a>b && a>c) printf("%d\n", (a<<k)+b+c);

	else if(b>a && b>c) printf("%d\n", a+(b<<k)+c);

	else printf("%d\n", a+b+(c<<k));

	return 0;

}