akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define vll vector<ll>
#define pll pair<ll , ll>
#define vpll vector<pair<ll, ll> >
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define N 100001
#define HOLE 1000000007

ll fn(ll x,ll rn[])
{
    if(rn[x]==x) return x;
    else return rn[x]=fn(rn[x],rn);
}

void un(ll x,ll y,ll rn[],ll sz[])
{
    x=fn(x,rn);
    y=fn(y,rn);
    if(x==y) return;
    if(sz[x]<sz[y]) swap(x,y);
    sz[x]+=sz[y];
    rn[y]=x;
    return;
}

ll power(ll x,ll y)
{
    ll res = 1; // Initialize result

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x)%HOLE;

        // n must be even now
        y = y >> 1; // y = y/2
        x = (x * x)%HOLE; // Change x to x^2
    }
    return res;
}

vector <ll> adjl[N];
ll marked[N]={0};
vector <ll> order;

void dfs (ll x){

    if(marked[x])
        return;
    marked[x]=1;

    REP(i,0,adjl[x].size()){

    }

    return;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll q=1;
    //cin>>q;
    while(q--){

        int flag=0;

        ll n;
        cin>>n;

        ll a[n];

        REP(i,0,n){
            cin>>a[i];
        }


        ll dp[n+1][2];
        dp[0][0]=0;
        dp[1][1]=a[0];
        dp[1][0]=0;

        REP(i,2,n+1){
            if(i%2){

                dp[i][0]=max(dp[i-2][0]+a[i-1],dp[i-1][0]);
                dp[i][1]=dp[i-2][1]+a[i-1];
            }
            else{
                dp[i][0]=max(dp[i-2][0]+a[i-1],dp[i-1][1]);
            }
        }

        cout<<dp[n][0]<<endl;


    }

return 0;
}


Measured memory_bytes: 10644
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(b>a*c)cout<<c<<endl;
    else cout<<b/a<<endl;
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> pii;

int main() {
  int H, N;
  cin >> H >> N;
  vector<int> A(N), B(N);
  int max_A = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    max_A = max(max_A, A[i]);
  }
  vector<int> dp(H + max_A, 0x3f3f3f3f);
  dp[0] = 0;
  for (int i = 1; i < H + max_A; i++) {
    for (int j = 0; j < N; j++) {
      if (i - A[j] >= 0) {
        dp[i] = min(dp[i], dp[i - A[j]] + B[j]);
      }
    }
  }
  int res = 0x3f3f3f3f;
  for (int i = H; i < H + max_A; i++) {
    if (dp[i] != 0) res = min(res, dp[i]);
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
  int N, M;
  cin >> N >> M;
  int ans=0;
  if(N!=1&&M!=1) {
    ans=N*M-2*(N+M-2);
  }
  else if(N==1&&M==1) {
    ans=1;
  }
  else {
    ans=max(N, M)-2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

int main(){
    int A, B, C, X, cnt = 0;
    cin >> A >> B >> C >> X;
    for(int i=0; i<=A; i++){
        for(int j=0; j<=B; j++){
            for(int k=0; k<=C; k++){
                if(500*i + 100*j + 50*k == X){
                    cnt += 1;
                }
            }
        }
    }
    cout << cnt;
}

Measured memory_bytes: 256
import sys

S_1 = list(input())
S_2 = list(input())
S_3 = list(input())

def trush(S_n):
    if S_n == "a":
        if len(S_1) == 0:
            print("A")
            sys.exit()
        trushed_c = S_1.pop(0)
        trush(trushed_c)
    elif S_n == "b":
        if len(S_2) == 0:
            print("B")
            sys.exit()
        trushed_c = S_2.pop(0)
        trush(trushed_c)
    else:
        if len (S_3) == 0:
            print("C")
            sys.exit()
        trushed_c = S_3.pop(0)
        trush(trushed_c)
            
trush(S_1[0])

Measured memory_bytes: 3188
#include <stdio.h>
#include <stdlib.h>

int main(){
  int n, m;  scanf("%d %d", &n, &m);
  int **graph;
  graph = (int **)malloc(sizeof(int*)*(n+5));
  for(int i=0; i<=n+1; i++)  graph[i] = (int *)malloc(sizeof(int)*(m+5));

  for(int i=0; i<m; i++){
    int a, b;  scanf("%d %d", &a, &b);
    graph[a][++graph[a][0]] = b;
    graph[b][++graph[b][0]] = a;
  }

  int visited[100005] = {0};
  visited[1] = 1;
  int ans[100005] = {0};
  int start = 0, end = 0;
  int will[200005] = {0};
  will[end++] = 1;
  while((end-start) != 0){
    int from = will[start];
    start = (start + 1) % 200005;
    for(int i=1; i<=graph[from][0]; i++){
      int to = graph[from][i];
      if(visited[to] == 0){
	visited[to] = 1;
	//	will[++will[0]] = to;
	will[end] = to;
	end = (end + 1) % 200005;
	ans[to] = from;
      }
    }
  }

  printf("Yes\n");
  for(int i=2; i<=n; i++){
    printf("%d\n", ans[i]);
  }  
  return 0;
}


Measured memory_bytes: 557324
#include<stdio.h>
#include<string.h>
int main(){
    char a[15],b[15],c[15];
    scanf("%s %s %s",a,b,c);
    getchar();
    if(a[strlen(a)-1]==b[0] && b[strlen(b)-1]==c[0]) puts("YES");
    else puts("NO");
    return 0;
}


Measured memory_bytes: 128
N, K = map(int, input().split())
XY = []
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    X.append(x)
    Y.append(y)
X.sort()
Y.sort()
ix = {v: i for i, v in enumerate(X)}
iy = {v: i for i, v in enumerate(Y)}
m = [[0] * (len(X) + 1) for _ in range(len(Y) + 1)]
for x, y in XY:
    m[iy[y] + 1][ix[x] + 1] += 1
for y in range(len(Y) + 1):
    for x in range(len(X)):
        m[y][x + 1] += m[y][x]
for x in range(len(X) + 1):
    for y in range(len(Y)):
        m[y + 1][x] += m[y][x]
ans = float("inf")
for x0 in range(len(X) - 1):
    for x1 in range(x0 + 1, len(X)):
        for y0 in range(len(Y) - 1):
            for y1 in range(y0 + 1, len(Y)):
                n = m[y1 + 1][x1 + 1] - m[y0][x1 + 1] - \
                    m[y1 + 1][x0] + m[y0][x0]
                if n >= K:
                    s = (X[x1] - X[x0]) * (Y[y1] - Y[y0])
                    ans = min(ans, s)
print(ans)


Measured memory_bytes: 44780
#include<bits/stdc++.h>
        #define ll long long
        #define rep(i,a,b) for(i=a;i<b;i++)
        #define pb push_back
        #define all(v) v.begin(),v.end()
        #define F first
        #define S second
        #define hell 1000000007
        using namespace std;
        const int N=500;
        void solve()
        {
            ll i,j,k,n,m,c=0,ans=0;
            string s;
            cin>>n;
            cout<<n+n*n+n*n*n;



    }

        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0);
            cout.tie(0);
            int t=1;
            //cin>>t;
            while(t--)
            solve();
        }


Measured memory_bytes: 3636
import numpy

n,m,x=map(int,input().split())

l=[]
for i in range(n):
    l.append(list(map(int,input().split())))

bl=[]
for i in range(2**n):
    bli=list(map(int,format(i,"b").zfill(n)))
    bl.append(bli)


p=-1
for i in range(2**n):
    u=numpy.zeros(m,dtype=int)
    pi=0
    for j in range(n):
        if bl[i][j]==1:
            pi+=l[j][0]
            for k in range(m):
                u[k]+=l[j][k+1]
    if min(u)>=x:
        if p==-1:
            p=pi
        else:
            p=min(p,pi)

print(p)

Measured memory_bytes: 27252
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[N];
ll ans;
map<int, int>mp;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		ans += mp[i - a[i]];
		mp[i + a[i]]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 21504
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))


n = ni()

s = [_ for _ in input()]

ans = []

last = ""
for i in range(n):
    if s[i] == last:
        continue
    ans += s[i]
    last = s[i]

print(len(ans))


Measured memory_bytes: 4632
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main()
{
std::string S;
std::string T;
cin >>S;
cin >>T;
int p=0;
for(int k=0;k<=S.size();k++){
if(S[k]!=T[k]){
p++;
}
}
if(p==1){
std::cout <<"Yes"<< std::endl;
}
else{
std::cout <<"No"<< std::endl;
}
return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int N, D, X;
    cin >> N >> D >> X;
    for(int i = 0; i < N; i++){
        int A;
        cin >> A;
        X += (D + A - 1) / A;
    }
    cout << X << endl;
}


Measured memory_bytes: 256
def bfs(g, N, s, t):
    from collections import deque

    dist = [-1] * (N * 3)
    dist[s] = 0

    dq = deque()
    dq.append(s)

    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = d + 1
            if u == t:
                return dist[t] // 3  # TLEしたので解を見つけたら即returnに変えた
            dq.append(u)
    return -1


def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N * 2)
        g[u + N * 2].add(v)

    S, T = (int(x) - 1 for x in input().split())

    ans = bfs(g, N, S, T)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 93708
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <vector>
using namespace std;

int main(){
    int N;
    cin >> N;
    int A[N+2];
    A[0] = A[N+1] = 0;
    for(int i = 0; i < N; i++){
        cin >> A[i+1];
    }
    int reduce[N];
    for(int i = 0; i < N; i++){
        reduce[i] = - abs(A[i+2] - A[i+1]) - abs(A[i+1] - A[i]) + abs(A[i+2] - A[i]);
    }
    // calc sum
    int sum = 0;
    for(int i = 0; i < N+1; i++){
        sum += abs(A[i+1] - A[i]);
    }
    for(int i = 0; i < N; i++){
        cout << sum + reduce[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 510000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
lli gcd(lli num1, lli num2){
    return num2 != 0 ? gcd(num2, num1 % num2) : num1;
}
lli lcm(lli num1, lli num2){
    return num1 / gcd(num1, num2) * num2;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli A,B,C,D,E,F,N,M,K,L,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> N;
  Out(N*(N-1)/2);
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;


int main() {
	
	int sum= 0;
	for (;;){
		string N;
		cin >> N;
		int n = N.size();
		if(N == "0") {
			break;
		}
		else {
			for (int i = 0; i < n; i++) {
				sum += N[i]-'0';
				
			}
			cout << sum << endl;
			sum = 0;
		}

		
	}
	return 0;
}


Measured memory_bytes: 3180
//============================================================================
//Everyone has a different way of thinking, so God Created us
//   Hope You Respect My Way..,Thank You ):
// Author      : Murad
// Name        : Codeforces.cpp & Atcoder.cpp
// Description : Problem name
//============================================================================
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define pi 3.1415926536
#define forn(i,a,b)for(int i=a;i<b;i++)
#define LL long long
#define ULL unsigned long long
#define MP make_pair
#define SZ(c) int(c.size())
#define ff first
#define ss second
#define INF 1e9 + 1
#define _INF INT32_MIN
#define PQ priority_queue
#define MM multimap
#define PB push_back
#define vii vector<int>
#define ipair pair<int,int>
#define lpair pair<LL,LL>
#define MAXN 100004
#define El3zba ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define modd 1000000007
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1,v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1,v2,v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
#define endl '\n'
//std::transform(s1.begin(), s1.end(), s1.begin(),::tolower);
char alphz[27] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
float Euclidean(LL x1, LL x2, LL y1, LL y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}
LL gcd(LL a,LL b) {
	LL c;
	while (a != 0) {
		c = a;
		a = b % a;
		b = c;
	}
	return b;
}
int LCM(int a, int b) {
	return (a*b) / gcd(a, b);
}
void PrimeFactor(LL n)
{
	while (n % 2 == 0) {
		printf("%d ", 2);
		n /= 2;
	}
	for (int i = 3; i <= sqrt(n); i += 2)
	{
		if (n%i == 0) {
			printf("%d ", i);
			n /= i;
		}
	}
	if (n > 2)printf("%d ", n);
}
bool is_square(LL x) {
	LL l = 0, r = x;
	while (l <= r) {
		LL mid = l + (r - l) / 2;
		if (mid*mid == x)return true;
		if (mid*mid > x)r = mid - 1;
		else l = mid + 1;
	}
	return false;
}
bool is_Prime(int x) {
	if (x == 2)return 1;
	else if (x % 2 == 0 || x < 2)return 0;
	for (int i = 3; i*i <= x; i += 2)
		if (x%i == 0)return 0;
	return 1;
}
void dijjkstra(int src, int n) {
	list<ipair>adj[1000005];
	vector<bool>visited(1000005, false);
	vector<int>dis(1000005, 1e9);
	PQ<ipair, vector<ipair>, greater<ipair>>pq;
	pq.push(MP(0, 1));
	dis[src] = 0;
	while (!pq.empty())
	{
		int u = pq.top().ss;
		visited[u] = true;
		pq.pop();
		list<ipair>::iterator i;
		for (i = adj[u].begin(); i != adj[u].end(); i++)
		{
			int v = i->ff;
			int we = i->ss;
			if (!visited[v] && dis[v] > dis[u] + we)
			{
				dis[v] = dis[u] + we;
				pq.push(MP(dis[v], v));
			}
		}
	}
}
int main()
{
	El3zba;
	/***  بسم الله الرحمن الرحيم   ***/
	int n;
	cin >> n;
	vector<int>a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int ans = gcd(a[0],a[1]);
	for (int i = 1; i < n; i++)
	{
		ans = min(ans, (int)gcd(ans, a[i]));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;




int main(int argc, char *argv[])
{
	int n;
	int a, b;
	vector<int> p;
	int ans;
	

	//input
	cin >> n;
	cin >> a >> b;
	for (int i = 0; i < n; i++){
		int pi;
		cin >> pi;
		p.push_back(pi);
	}


	//sort
	sort(p.begin(), p.end());


	//calc
	int q1count = 0;
	int q2count = 0;
	int q3count = 0;
	for (int i = 0; i < n; i++){
		if (p[i] <= a){
			q1count++;
		}
		if (a < p[i] && p[i] <= b){
			q2count++;
		}
		if (b < p[i]){
			q3count++;
		}
	}

	ans = min(min(q1count, q2count), q3count);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class BHomework {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      ll n, m; cin >> n >> m;
      ll sum = 0;
      rep(i, m) {
        ll a; cin >> a;
        sum += a;
      }
      ll r = n - sum;
      chmax(r, -1LL);
      cout << r << endl;
    }
};

signed main() {
  BHomework solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;

long long sum(long long n)
{
	long long su = 0;
	while(n)
	{
		long long rem = n%10;
		su+=rem;
		n/=10;
	}
	return su;
}

int main()
{
	
	
	long long n;
	cin >> n;
	if(n % sum(n) == 0) cout << "Yes\n";
	else cout << "No\n";
	
	
	
	
	
	return 0;
}

Measured memory_bytes: 256
H, W=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
a=[list(map(int,input().split())) for _ in range(H)]
ans=0

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])

for i in range(H):
    for j in range(W):
        if a[i][j]>=0:
            ans += c[a[i][j]][1]

print(ans)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int Maxn = 3005;
const int mod = 1000000007;
const int inv2 = 500000004;

int n, q;
int a[Maxn];
int qa[Maxn], qb[Maxn];
int nxt[Maxn][Maxn];
int dpa[Maxn][Maxn], dpb[Maxn][Maxn];
int res;

int Get(int from, int a, int b)
{
    int r = min(nxt[from][a], nxt[from][b]);
    if (r >= q) return a < b;
    if (qa[r] == a) return dpa[r][b];
    if (qa[r] == b) return (1 - dpa[r][a] + mod) % mod;
    if (qb[r] == a) return dpb[r][b];
    if (qb[r] == b) return (1 - dpb[r][a] + mod) % mod;
}

int Change(int quer, int x)
{
    if (qa[quer] == x) x = qb[quer];
    else if (qb[quer] == x) x = qa[quer];
    return x;
}

int main()
{
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &qa[i], &qb[i]);
        qa[i]--; qb[i]--;
    }
    for (int j = 0; j < n; j++)
        nxt[q][j] = q;
    for (int i = q - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++)
            nxt[i][j] = nxt[i + 1][j];
        nxt[i][qa[i]] = nxt[i][qb[i]] = i;
        for (int j = 0; j < n; j++) {
            if (j != qa[i]) {
                int a = qa[i], b = j;
                int lst = Get(i + 1, a, b);
                a = Change(i, a), b = Change(i, b);
                dpa[i][j] = ll(lst + Get(i + 1, a, b)) * inv2 % mod;
            }
            if (j != qb[i]) {
                int a = qb[i], b = j;
                int lst = Get(i + 1, a, b);
                a = Change(i, a), b = Change(i, b);
                dpb[i][j] = ll(lst + Get(i + 1, a, b)) * inv2 % mod;
            }
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (a[i] > a[j])
            res = (res + Get(0, i, j)) % mod;
    while (q--)
        res = 2ll * res % mod;
    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 106112
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  vi32 a(n), b(n);
  cin >> a >> b;
  i64 asum = 0;
  i64 bsum = 0;
  rep(i, n) asum += a[i];
  rep(i, n) bsum += b[i];
  if (asum < bsum) {
    cout << -1 << endl;
    return;
  }
  int ans = 0;
  i64 must = 0;
  vi32 lst;
  rep(i, n) {
    if (a[i] < b[i]) ans++, must += b[i] - a[i];
    if (a[i] > b[i]) lst.push_back(a[i] - b[i]);
  }
  sort(all(lst));
  while (must > 0) {
    ans++;
    must -= lst.back();
    lst.pop_back();
  }
  cout << ans << endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#define maxn 200005
using namespace std;
vector <int> G[maxn];
map <int, int> q[maxn];
int m[maxn], ans[maxn];
void get_m(int u, int f){
	m[u] = max(m[f], f);
	for (int i = 0; i < G[u].size(); ++ i){
		int v = G[u][i];
		if (v != f)
			get_m(v, u);
	}
}
void get_q(int u, int f, int x){
	if (q[u].count(x))
		return;
	int ans = 0;
	for (int i = 0; i < G[u].size(); ++ i){
		int v = G[u][i];
		if (v != f && v <= x){
			get_q(v, u, x);
			ans += 1 + q[v][x];
		}
	}
	q[u][x] = ans;
}
void solve(int u, int f){
	for (int i = 0; i < G[u].size(); ++ i){
		int v = G[u][i];
		if (v != f){
			if (v > m[u]){
				get_q(v, u, m[v]);
				ans[v] = ans[u] + q[v][m[v]] + 1;
			}
			else{
				get_q(v, u, m[v]);
				get_q(v, u, m[u]);
				ans[v] = ans[u] + q[v][m[v]] - q[v][m[u]];
			}
			solve(v, u);
		}
	}
}
int main(){
	int n;
	cin >> n;
	for (int i = 1; i < n; ++ i){
		int x, y;
		scanf("%d %d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	get_m(1, 0);
	ans[1] = 0;
	solve(1, 0);
	for (int i = 2; i <= n; ++ i)
		printf("%d ", ans[i]);
}


Measured memory_bytes: 60928
#include<bits/stdc++.h>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
#define out(x) cout<<x<<"\n";
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}

ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

int n;

void solve(){
  vector<int>imos(90000+5);
  rep(i,n){
    string s,t;
    cin>>s>>t;
    int sh=(s[0]-'0')*36000+(s[1]-'0')*3600;
    int sm=(s[3]-'0')*600+(s[4]-'0')*60;
    int ss=(s[6]-'0')*10+(s[7]-'0');
    int th=(t[0]-'0')*36000+(t[1]-'0')*3600;
    int tm=(t[3]-'0')*600+(t[4]-'0')*60;
    int ts=(t[6]-'0')*10+(t[7]-'0');
    imos[sh+sm+ss]++;
    imos[th+tm+ts]--;
  }
  int ans=0;
  rep(i,9e4)imos[i+1]+=imos[i];
  rep(i,9e4)chmax(ans,imos[i]);
  cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(15);
    while(1){
      cin>>n;
      if(n==0)break;
      solve();
    }
    //solve();
    return 0;
}



Measured memory_bytes: 3576
import java.io.*;
import java.util.*;

public class Main {
    public static void main(final String[] args) {
        final FastReader s=new FastReader();
        String st = s.nextLine();
        int count=0;
        int local = 0;
        for (char c : st.toCharArray()) {
            if(c=='R'){
                    local++;
            } else {
                count = Math.max(count, local);
                local=0;
            }
        }
        count = Math.max(count, local);
        System.out.println(count);
    }

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (final IOException  e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }
        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try { str = br.readLine(); }
            catch (final IOException e) { e.printStackTrace(); }
            return str;
        }
    }
}

Measured memory_bytes: 25360
s = input()
x,y = map(int,input().split(" "))
l = [len(c) for c in s.split("T")]
X = l[::2]
Y = l[1::2]

ansX = [X[0]]
for i in range(1,len(X)):
    if not X[i] == 0:
        ansX = list(set([c+X[i] for c in ansX]+[c-X[i] for c in ansX]))

ansY = [0]
for i in range(0,len(Y)):
    if not Y[i] == 0:
        ansY = list(set([c+Y[i] for c in ansY]+[c-Y[i] for c in ansY]))
    
if x in ansX and y in ansY:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 3876
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = x * 10 + (c ^ 48), c = nc;
  return x;
  #undef nc
}

typedef long long ll;

void solve() {
  ll A, X, B, Y, T;
  cin >> A >> X >> B >> Y >> T;
  if (X <= Y) {
    puts("NO"); return;
  }
  puts((A < B && A + X * T >= B + Y * T) || (A > B && A - X * T <= B - Y * T) ? "YES" : "NO");
}

int main() {
//  int T = read();
//  while (T--) solve();
  solve();
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A;
  int B;
  int C;
  int D;
  int L;
  int R;
  
  cin >> A >> B >> C >> D;
  
  L = A + B;
  R = C + D;
  
  if (L > R) {
    cout << "Left" << endl;
  } else if (L == R) {
    cout << "Balanced" << endl;
  } else if (L < R) {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
s = list(raw_input())
for loop in xrange(input()):
    c = raw_input().split()
    if c[0] == "replace":
        s[int(c[1]): int(c[2]) + 1] = list(c[3])
    if c[0] == "reverse":
        s[int(c[1]): int(c[2]) + 1] = s[int(c[1]): int(c[2]) + 1][::-1]
    if c[0] == "print":
        print "".join(s[int(c[1]): int(c[2]) + 1])

Measured memory_bytes: 4256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int INF = 1<<30;
string convert(int num){
  string s = to_string((num));
  string zero((6-int(s.size())), '0');
  return zero+s;
}
int main(){
  int n, m;cin>>n>>m;
  vector<P> city(m); // pref, year
  vector<vector<P>> pref(n); // year, index
  for(int i=0;i<m;i++){
  	cin>>city[i].first>>city[i].second;
    pref[city[i].first-1].push_back(P(city[i].second, i));
  }
  for(int i=0;i<n;i++){
  	sort(pref[i].begin(), pref[i].end());
    for(int j=0;j<(int)pref[i].size();j++){
      city[pref[i][j].second].second=j+1;
    }
  }
  for(int i=0;i<m;i++){
  	cout<<convert(city[i].first)<<convert(city[i].second)<<endl;
  }
}

Measured memory_bytes: 7808
#include<iostream>
using namespace std;
int main()
{

int n,d,x; // n people; d days; x remainings
cin>>n>>d>>x;
int s[111];
for(int i=0;i<n;i++)
    cin>>s[i];
int ans=0;

for(int i=0;i<n;i++)
    ans+=(d-1)/s[i]+1;
ans+=x;
cout<<ans;

system("pause");
return 0;
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,ans = 0;
  cin >> n;
  for(int i = 0;i < n;i++){
    long a;
    cin >> a;
    while(a%2 == 0){
      a /= 2;
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val mod = 1000000007L
    fun pow(a: Long, b: Long): Long {
        var bt = b
        var ret: Long = 1
        var tmp = a
        while (bt > 0) {
            if (bt and 1 == 1L) ret = ret * tmp % mod
            tmp = tmp * tmp % mod
            bt = bt shr 1
        }
        return ret
    }

    fun nCk(n: Long, k: Long): Long {
        var ret: Long = 1
        val min = Math.min(k, n - k)
        for (i in 1..min) {
            ret = ret * pow(i, (mod - 2)) % mod
        }
        for (i in n - min + 1..n) {
            ret = ret * i % mod
        }
        return ret
    }
    val (n, a, b) = readLine()!!.split(' ').map(String::toLong)
    var base = pow(2, n) - 1 + mod
    val minus = (nCk(n, a) + nCk(n, b))%mod
    println((base - minus) % mod)
}


Measured memory_bytes: 38292
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cassert>
#include <utility>
#include <numeric>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for (int i=0; i<(n); ++i)

using namespace std;
using ll = long long;

int main (){   
    int N;
    
    cin >> N;
    vector<int> A(N);
    for (int i=0;i<N;i++){
        cin >> A[i];
    }
    bool fag = true;
    for (int i=0;i<N;i++){
        if(A[i]%2 == 0){
            if(!(A[i]%3 == 0 || A[i]%5 == 0)){
                fag = false;
                break;
            }
        }
    }

    if(fag){
        cout << "APPROVED";
    }
    else cout << "DENIED";

}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int a[] = new int[m];
        int b[] = new int[m];

        HashMap<Integer, Boolean> alist = new HashMap<Integer, Boolean>();
        HashMap<Integer, Boolean> blist = new HashMap<Integer, Boolean>();

        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }

        for (int i = 0; i < m; i++) {
            if (a[i] == 1) {
                alist.put(b[i], true);
            }

            if (b[i] == n) {
                blist.put(a[i], true);
            }
        }

        for (int i = 2; i <= n; i++) {
            if (alist.containsKey(i) && blist.containsKey(i)) {
                System.out.println("POSSIBLE");
                return;
            }
        }
        System.out.println("IMPOSSIBLE");
    }
}


Measured memory_bytes: 96460
#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;

int main() {
	int n=0;
	int a[1005],b[1005];
	int c[1005];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
	}
	for(int i=0;i<n;i++){
		c[i]=abs(a[i]-b[i]);
	}
	double sum1=0,sum2=0,sum3=0,max=0;
	for(int i=0;i<n;i++){
		sum1+=c[i];
		sum2+=c[i]*c[i];
		sum3+=c[i]*c[i]*c[i];
		if(max<c[i]){
			max=c[i];
		}
	}
	cout.precision(6);

	printf("%lf\n%lf\n%lf\n%lf\n",sum1,pow(sum2,0.5),pow(sum3,1.0/3),max);
	return 0;
}

Measured memory_bytes: 3324
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define mp std::make_pair
#define pb push_back
#define MOD 1000000007
typedef long long ll;
int lst[5005], to[10005], pre[10005], tot, sz[5005], dp_sz[5005];
ll dp[5005][5005][2], pw[5005], tmp[5005][2];
inline void add_edge(int u, int v)
{
	to[tot] = v;
	pre[tot] = lst[u];
	lst[u] = tot++;
}
void init(int u, int fa = -1)
{
	sz[u] = 1;
	for (int i = lst[u]; ~i; i = pre[i])
	{
		if (to[i] == fa)
			continue;
		init(to[i], u);
		sz[u] += sz[to[i]];
	}
}
inline ll calc(int x)
{
	return x & 1 ? 0 : pw[x >> 1];
}
void dfs(int u, int fa = -1)
{
	dp[u][0][0] = 1;
	for (int i = lst[u]; ~i; i = pre[i])
	{
		int v = to[i];
		if (v == fa)
			continue;
		dfs(v, u);
		memset(tmp, 0, sizeof(tmp));
		for (int x = dp_sz[u]; x >= 0; x--)
		{
			for (int y = dp_sz[v]; y >= 0; y--)
			{
				(tmp[x + y][0] += dp[u][x][0] * dp[v][y][0]) %= MOD;
				(tmp[x + y][0] += dp[u][x][1] * dp[v][y][1]) %= MOD;
				(tmp[x + y][1] += dp[u][x][0] * dp[v][y][1]) %= MOD;
				(tmp[x + y][1] += dp[u][x][1] * dp[v][y][0]) %= MOD;
			}
		}
		memcpy(dp[u], tmp, sizeof(tmp));
		dp_sz[u] += dp_sz[v];
	}
	if (u)
	{
		for (int x = dp_sz[u]; x >= 0; x--)
		{
			(dp[u][sz[u]][0] += dp[u][x][1] * calc(sz[u] - x)) %= MOD;
			(dp[u][sz[u]][1] += dp[u][x][0] * calc(sz[u] - x)) %= MOD;
		}
	}
	dp_sz[u]++;
	// printf("%d\n", u);
	// for (int i = 0; i <= dp_sz[u]; i++)
	// 	printf("%lld %lld\n", dp[u][i][0], dp[u][i][1]);
}
int main()
{
	// freopen("ARC101-E.in", "r", stdin);
	memset(lst, -1, sizeof(lst));
	int n;
	scanf("%d", &n);
	pw[0] = 1;
	for (int i = 1; i <= n; i++)
		pw[i] = pw[i - 1] * (i * 2 - 1) % MOD;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(--u, --v);
		add_edge(v, u);
	}
	init(0);
	dfs(0);
	ll ans = 0;
	for (int i = 0; i <= n; i++)
	{
		(ans += dp[0][i][0] * calc(n - i)) %= MOD;
		(ans -= dp[0][i][1] * calc(n - i)) %= MOD;
	}
	printf("%lld\n", (ans + MOD) % MOD);
	return 0;
}


Measured memory_bytes: 392064
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

using namespace std;
typedef pair<int, int> P;

#define pi 3.141592653589793)
#define mod 1000000007

int A, B, K;

void solve() {
	cin >> A >> B >> K;
	if (2 * K >= B - A + 1) {
		for (int i = A; i <= B; i++) cout << i << endl;
	}
	else {
		for (int i = 0; i < K; i++) cout << A + i << endl;
		for (int i = K-1; i >= 0; i--) cout << B - i << endl;
	}
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int ninjou(int n){
  int a=1;
  for (int i=0;i<n;i++){
    a *= 2;
  }
  return a;
}

int main (){
  int N;
  cin >>N;
  
  for (int i=0;i<7;i++){
    if(ninjou(i)<=N && ninjou(i+1)>N){
      cout << ninjou(i) << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;

int tower_length(int n){
  int i;
  int len = 0;
  for(i=1;i<=n;i++){
    len += i;
  }
  return len;
}

int main(){
  int a,b;
  cin >> a >> b;
  int n = b - a - 1;
  cout << tower_length(n) - a << endl;
  return 0;
}


Measured memory_bytes: 256
def check(N,target,A,K):
  cnt = 0
  for i in range(N):
    cnt += -(-A[i]//target)-1
  if cnt>K:
    return False
  return True

def solve():
  ans = 0
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  low = 1
  high = 10**9+1
  mid = (low+high)//2
  while high>low+1:
    if check(N,mid,A,K):
      high = mid
    else:
      low = mid
    mid = (low+high)//2
  if check(N,low,A,K):
    ans = low
  else:
    ans = high
  return ans
print(solve())


Measured memory_bytes: 31044
def main():
    import sys
    sys.setrecursionlimit(311111)
    # import numpy as np
    ikimasu = sys.stdin.buffer.readline
    ini = lambda: int(ins())
    ina = lambda: list(map(int, ikimasu().split()))
    ins = lambda: ikimasu().strip()
    n,k = ina()
    tmp = ina()
    x = 1<<55
    rick = 0
    used = 0
    for _ in range(55+1):
        tmp1 = 0
        for i in tmp:
            if(i&x):
                tmp1+=1
        if(tmp1>=(n-tmp1)):
            rick+=x*tmp1
        else:
            if((x+used<=k)):
                rick+=x*(n-tmp1)
                used +=x
            else:
                rick+=x*tmp1
        x>>=1
    print(rick)


    


        
        
        


    
        


        


    




















if __name__ == "__main__":
    main()


Measured memory_bytes: 85132
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = 0
for i in range(n - 1):
    if a[i] + 1 == a[i + 1]:
        ans += c[a[i]-1]

print(ans + sum(b))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

signed main() {
  init();
  string S;
  cin >> S;
  REVERSE(S);

  ll N = 13;
  ll mod = 1000000007;
  vll dp(N, 0);

  dp[0] = 1;
  ll mul = 1;
  rep(i, S.size()) {
    vll next_dp(N, 0);
    if (S[i] == '?') {
      rep(num, 10) {
        rep(j, N) {
          next_dp[(num * mul + j) % N] += dp[j];
          next_dp[(num * mul + j) % N] %= mod;
        }
      }
    } else {
      ll num = S[i] - '0';
      rep(j, N) {
        next_dp[(num * mul + j) % N] += dp[j];
        next_dp[(num * mul + j) % N] %= mod;
      }
    }
    mul *= 10;
    mul %= N;
    dp = next_dp;
  }

  ll ans = dp[5];
  COUT(ans);
  return 0;
}

Measured memory_bytes: 512
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.sqrt
import kotlin.math.tan

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val s = br.readLine()!!
    val r = s.count { it == 'R' }
    val ans = if (r == 0) {
        0
    } else if (r == 1) {
        1
    } else if(r == 3){
        3
    } else {
        if (s == "RSR") {
            1
        } else {
            2
        }
    }
    out.println(ans)
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 34400
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  string s; cin >> s;
  cout << s + (s.back() == 's' ? "es" : "s") << '\n';
  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = (x << 3) + (x << 1) + (c ^ 48), c = nc;
  return x;
  #undef nc
}

typedef long long ll;
int n;
char str[10010];

bool check(char *s, int len) {
//  rep(i, 1, len) putchar(s[i]);
//  puts("");
  rep(i, 1, len / 2) {
    if (s[i] != s[len - i + 1]) return 0;
  }
  return 1;
}

int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  puts(check(str, n) && check(str, (n - 1) / 2) && check(str + (n + 3) / 2 - 1, n - (n + 3) / 2 + 1) ? "Yes" : "No");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int h, w;
vector<vector<bool>> flg(55, vector<bool>(55));
vector<vector<char>> hw(55, vector<char>(55));
int main() {
    cin >> h >> w;
    rep(i, h) rep(j, w) cin >> hw[i][j];
    int dx[4] = {1, -1, 0,  0};
    int dy[4] = {0,  0, 1, -1};
    rep(i, h) rep(j, w) {
        bool found = false;
        if ( hw[i][j] == '#' ) {
            rep(k, 4) {
                if ( i+dy[k] <  h                &&
                     i+dy[k] >= 0                &&
                     j+dx[k] <  w                &&
                     j+dx[k] >= 0                ) {
                    if ( hw[i+dy[k]][j+dx[k]] == '#' ) {
                        found = true;
                    }
                }
            }
            if ( !found ) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
lines = $stdin.read
array = lines.split("\n")

Q,H,S,D = array[0].split(" ").map(&:to_i)
N = array[1].to_i

litter = {}
litter[:q] = 0.25
litter[:h] = 0.5
litter[:s] = 1
litter[:d] = 2

#
# nリットル
#
def most_cheap_with_four(n)
  prices = {}
  times  = {}

  prices[:q] = (n/0.25) * Q if n/0.25 != 0
  prices[:h] = (n/0.5)  * H if n/0.5  != 0
  prices[:s] = (n/1)    * S if n/1    != 0
  prices[:d] = (n/2)    * D if n/2    != 0

  times[:q]  = n/0.25       if n/0.25 != 0
  times[:h]  = n/0.5        if n/0.5  != 0
  times[:s]  = n/1          if n/1    != 0
  times[:d]  = n/2          if n/2    != 0

  # puts "#{(n/0.25) * Q} yen"
  # puts "#{(n/0.5)  * H} yen"
  # puts "#{(n/1)    * S} yen"
  # puts "#{(n/2)    * D} yen"

  m = prices.sort_by { |key, value| value }.first
  # [:kind, :sum, :times]
  { kind: m[0], sum: m[1].floor, times: times[m[0]].floor }
end

n = N
summary = 0

while n != 0
  ret = most_cheap_with_four(n)
  n = n - litter[ret[:kind]] * ret[:times]
  #puts ret.to_s
  summary = summary + ret[:sum]
  #puts summary.floor
end

puts summary.floor


Measured memory_bytes: 1788
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

struct UnionFind{
  ll N;
  llvec p;
  llvec cnt;
  UnionFind(ll n){
    N = n;
    p=llvec(N);
    cnt=llvec(N, 0);
    rep(i, N){
      p[i] = i;
      cnt[i] = 1;
    }
  }

  void con(ll a, ll b){
    P at = root(a);
    P bt = root(b);
    if(at.second!=bt.second){
      if(at.first>bt.first){
        swap(at, bt);
        swap(a, b);
      }
      p[at.second] = bt.second;
      cnt[bt.second]+=cnt[at.second];
      p[a]=bt.second;
    }
  }

  P root(ll a){
    ll atmp = a;
    ll c=0;
    while(atmp!=p[atmp]){
      atmp = p[atmp];
      c++;
    }
    p[a] = atmp;
    return {c, atmp};
  }

  bool is_con(ll a, ll b){
    P at=root(a);
    P bt=root(b);
    return at.second == bt.second;
  }
  
};

struct dijkstra{
  ll N;
  llvec d;
  vector<vector<edge>> e;
  dijkstra(ll n){
    N = n;
    //d = llvec(N, 1e18);
    e = vector<vector<edge>>(N);
  }

  void add_edge(ll from, ll to, ll cost){
    e[from].push_back({to, cost});
  }

  void run(ll start){
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    d = llvec(N, 1e18);
    d[start]=0;
    while(!que.empty()){
      P q = que.top();que.pop();
      ll dc = q.first;
      ll x = q.second;
      if(dc>d[x]){
        continue;
      }else{
        for(auto ip: e[x]){
          if(d[ip.x]<=d[x]+ip.c){
            continue;
          }else{
            d[ip.x]= d[x]+ip.c;
            que.push({d[ip.x], ip.x});
          }
        }
      }
    }
  }  
};


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N;
  string S;
  cin >> N >> S;
  llvec L(N), R(N);
  rep(i, N){
    L[i]=(S[i]=='W'?1:0);
    if(i>=1)L[i]+=L[i-1];
  }
  rrep(i, N){
    R[i]=(S[i]=='E'?1:0);
    if(i+1<=N-1)R[i]+=R[i+1];
  }
  //DUMP(i, L);cerr << endl;
  //DUMP(i, R);cerr << endl;
  
  ll ans = 1e18;
  rep(i, N){
    ll tmp=0;
    if(i-1>=0)tmp += L[i-1];
    if(i+1<=N-1)tmp += R[i+1];
    ans = min(ans, tmp);
  }

  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 5380