akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

const int N = 2e5+10;

using namespace std;

main()
{
    fast;
    int n,k,i;
    cin>>n>>k;
    int mark[N]={0};
    for (i=1;i<=n;i++)
        mark[i%k]++;
    ll ans=pow(mark[0],3);
    if (k%2==0)
        ans+=pow(mark[k/2],3);
    cout<<ans<<endl;
}

Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
#include<map>
#include<string>
using namespace std;

int main(){
  map<string, int> a;
  int n, m;
  cin >> n;
  string s;
  for(int i=0; i<n; ++i){
    cin >> s;
    a[s]++;
  }

  cin >> m;
  string t;
  for(int i=0; i<m; ++i){
    cin >> t;
    a[t]--;
  }

  int ans = 0;
  for(auto itr=a.begin(); itr!=a.end(); ++itr){
    ans = max(ans, itr->second);
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
  int N;
  cin >> N;

  vector<int> W;

  for (int n=0; n<N; ++n) {
    int w;
    cin >> w;
    W.push_back(w);
  }

  int S1 = W[0], S2 = 0;
  for (int n=1; n<N; ++n)
    S2 += W[n];

  int min_diff = abs(S2 - S1);

  for (int n=1; n<N-1; ++n) {
    S1 += W[n];
    S2 -= W[n];

    min_diff = min(min_diff, abs(S2-S1));
  }
  
  cout << min_diff << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

struct Point { double x, y; };

void koch(int n, Point a, Point b){
    if(n == 0)return;
    Point s, t, u;
    double th = M_PI * 60 / 180.0;
    s.x = (2.0*a.x + 1.0*b.x) / 3.0;
    s.y = (2.0*a.y + 1.0*b.y) / 3.0;
    t.x = (1.0*a.x + 2.0*b.x) / 3.0;
    t.y = (1.0*a.y + 2.0*b.y) / 3.0;
    u.x = (t.x-s.x) * cos(th) - (t.y-s.y) * sin(th) + s.x;
    u.y = (t.x-s.x) * sin(th) + (t.y-s.y) * cos(th) + s.y;

    koch(n-1, a, s);
    printf("%.8f %.8f\n", s.x, s.y);
    koch(n-1, s, u);
    printf("%.8f %.8f\n", u.x, u.y);
    koch(n-1, u, t);
    printf("%.8f %.8f\n", t.x, t.y);
    koch(n-1, t, b);
}

int main(){
    Point a, b;
    int n;

    scanf("%d", &n);

    a.x=0;
    a.y=0;
    b.x=100;
    b.y=0;

    printf("%.8f %.8f\n", a.x, a.y);
    koch(n, a, b);
    printf("%.8f %.8f\n", b.x, b.y);

    return 0;
}


Measured memory_bytes: 2700
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
prev = -10
for e in a:
  ans += b[e-1]
  if e==prev+1:
    ans += c[prev-1]
  prev = e
print(ans)

Measured memory_bytes: 38384
#include <stdio.h>

int main(void)
{
	int a, b;
	int c100, c500, c1000;
	
	while (1){
		scanf("%d%d", &a, &b);
		if (a == 0 && b == 0){
			break;
		}
		
		b -= a;
		
		c1000 = b / 1000;
		b = b % 1000;

		c500 = b / 500;
		b = b % 500;
	
		c100 = b / 100;
		b = b % 100;

		printf("%d %d %d\n", c100, c500, c1000);
	}
	
	return (0);
}

Measured memory_bytes: 596
#include<iostream>
#include<math.h>
#include<string>
#include<map>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<time.h>
#include<random>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int p, q;
int cntt = 0;
int cnt = 0;
int now = 0;
int n;
int pp, qq;
vector<bool>visited(10,false);
void dfs(int t) {
	if (t == n) {
		cnt++;
		if (now == p) {
			pp = cnt;
		}
		if (now == q) {
			qq = cnt;
		}
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			now *= 10;
			now += i;
			dfs(t + 1);
			now /= 10;
			visited[i] = false;
		}
	}
}
int main() {
	cin >> n;
	rep(i, n) {
		int a;
		cin >> a;
		p *= 10;
		p += a;
	}
	rep(i, n) {
		int a;
		cin >> a;
		q *= 10;
		q += a;
	}
	dfs(0);
	cout << abs(pp - qq) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
main()
{
    int n,l,s=0;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int max=a[0];
    for(int i=0;i<n;i++){
        s+=a[i];
        if(max<a[i]){
            max=a[i];
        }
    }
    if((s-max)>max){
       printf("Yes\n");
       }
     else{
        printf("No\n");
     }
     return 0;
}


Measured memory_bytes: 1644
s=input()
t=input()


kouho=[]
for i in range(len(s)-len(t)+1):
    ans=s[:i]
    tmp=s[i:(i+len(t))]

    for j in range(len(t)):
        if tmp[j]==t[j]:
            ans+=t[j]
        elif tmp[j]=='?': 
            ans+=t[j]
        elif tmp[j]!='?' and tmp[j]!=t[j]:
            break
    ans=ans+s[(i+len(t)):]

    if len(ans)==len(s):
        kouho.append(ans)

if len(kouho)==0:
    print('UNRESTORABLE')
    exit(0)

answers=[]
for j in kouho:

    tmp_ans=''
    for k in range(len(j)):
        if j[k]=='?':
            tmp_ans+='a'
        else:
            tmp_ans+=j[k]

    answers.append(tmp_ans)

answers=sorted(answers)
print(answers[0])






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

enum Direction { TATE, YOKO } last;
constexpr int MOD = 1000000007;

int main() {
  int64_t N, sum;
  string S1, S2;
  cin >> N >> S1 >> S2;
  for (int i = 0; i < N; ++i) {
    Direction now = S1[i] == S2[i] ? TATE : YOKO;
    if (i == 0) {
      if (now == TATE) {
        sum = 3;
      } else {
        sum = 6;
        ++i;
      }
    } else {
      if (now == TATE) {
        sum = sum * (last == TATE ? 2 : 1) % MOD;
      } else {
        sum = sum * (last == TATE ? 2 : 3) % MOD;
        ++i;
      }
    }
    last = now;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
{-# LANGUAGE OverloadedStrings #-}
import           Data.Attoparsec.ByteString.Char8
import qualified Data.ByteString.Char8            as B
import qualified Data.IntSet                      as S

main :: IO ()
main = do
  Right ns <- parseOnly (decimal `sepBy` space) <$> B.getLine
  B.putStrLn $ if solve ns then "YES" else "NO"

solve :: [Int] -> Bool
solve ns = S.fromList ns == S.fromList [1,9,7,4]


Measured memory_bytes: 508
/* Dice2*/
#include <stdio.h>

int main(void)
{
    int Dice[6];
    scanf("%d %d %d %d %d %d", &Dice[0], &Dice[1], &Dice[2], &Dice[3], &Dice[4], &Dice[5]);
    int i;
    int q;
    scanf("%d", &q);
    int x, y;
    for(i = 0; i < q; i++){
        scanf("%d %d", &x, &y);
        if((x == Dice[0] && y == Dice[1]) || (x == Dice[4] && y == Dice[0]) || (x == Dice[5] && y == Dice[4]) || (x == Dice[1] && y == Dice[5])){
            printf("%d\n", Dice[2]);
        }else if((x == Dice[0] && y == Dice[2]) || (x == Dice[2] && y == Dice[5]) || (x == Dice[5] && y == Dice[3]) || (x == Dice[3] && y == Dice[0])){
            printf("%d\n", Dice[4]);
        }else if((x == Dice[0] && y == Dice[3]) || (x == Dice[3] && y == Dice[5]) || (x == Dice[5] && y == Dice[2]) || (x == Dice[2] && y == Dice[0])){
            printf("%d\n", Dice[1]);
        }else if((x == Dice[0] && y == Dice[4]) || (x == Dice[4] && y == Dice[5]) || (x == Dice[5] && y == Dice[1]) || (x == Dice[1] && y == Dice[0])){
            printf("%d\n", Dice[3]);
        }else if((x == Dice[1] && y == Dice[3]) || (x == Dice[3] && y == Dice[4]) || (x == Dice[4] && y == Dice[2]) || (x == Dice[2] && y == Dice[1])){
            printf("%d\n", Dice[5]);
        }else{
            printf("%d\n", Dice[0]);
        }
    }
    
    return 0;
}


Measured memory_bytes: 2108
B='{:041b}'.format
n,k,*a=map(int,open(0).read().split())
if not k:
  print(sum(a))
  exit()
l=[0]*41
for i in a:
  for j,t in enumerate(B(i)):
    if int(t):l[j]+=1
dp=[[0,-1]for i in range(41)]
for i,f in enumerate(map(int,B(k))):
  if not i:continue
  v=pow(2,40-i)
  v0,v1=(n-l[i])*v,l[i]*v
  if f:
    dp[i][0]=dp[i-1][0]+v0
    if dp[i-1][1]>=0:
      dp[i][1]=max(dp[i-1][0]+v1,dp[i-1][1]+max(v0,v1))
    else:
      dp[i][1]=dp[i-1][0]+v1
  else:
    dp[i][0]=dp[i-1][0]+v1
    if dp[i-1][1]>=0:
      dp[i][1]=dp[i-1][1]+max(v0,v1)
print(max(dp[-1]))

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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int k;
  cin >> k;

  vector<uint64_t> costs(k, INT_MAX);
  priority_queue<pair<uint64_t, int>, vector<pair<uint64_t, int>>,
                 greater<pair<uint64_t, int>>>
      q;
  costs[1] = 0;
  q.push(make_pair(0, 1));
  while (!q.empty()) {
    auto v = q.top();
    q.pop();
    int byten = (v.second * 10) % k;
    if (v.first < costs[byten]) {
      costs[byten] = v.first;
      q.push(make_pair(v.first, byten));
    }
    int next = (v.second + 1) % k;
    if (v.first + 1 < costs[next]) {
      costs[next] = v.first + 1;
      q.push(make_pair(v.first + 1, next));
    }
  }

  cout << costs[0] + 1 << "\n";
}


Measured memory_bytes: 2168
# Aizu Problem 0113: Period

#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def repeating_decimals(n, d):
    pre = n // d
    m = n - pre * d
    if m == 0:
        return "0", ""
    remains = []
    fraction = []
    while True:
        k = m // d
        fraction.append(k)
        m = m - k * d
        if m in remains:
            remains.append(m)
            break
        remains.append(m)
        if m == 0:
            return ''.join([str(x) for x in fraction[1:]]), ""
        m *= 10
    # fraction is periodic at this point:
    fraction = fraction[1:]
    idx = remains.index(m)
    non_periodic = ''.join([str(x) for x in fraction[:idx]])
    periodic = ''.join([str(x) for x in fraction[idx:]])
    return non_periodic, periodic


for line in sys.stdin:
    p, q = [int(_) for _ in line.split()]
    p1, p2 = repeating_decimals(p, q)
    print(p1 + p2)
    if len(p2) > 0:
        print(' ' * len(p1) + '^' * len(p2))

Measured memory_bytes: 7956
#include <cstddef>
#include <complex>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <limits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>

using ll = long long;
using ull = unsigned long long;

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

// ll frac_a_b(ll a, ll b)
// {
//     auto ans{1ll};

//     if (a < b)
//         std::swap(a, b);

//     for (auto i = a + b, j = 1ll; i > a; --i, ++j)
//     {
//         ans *= i;
//         if (j <= b)
//             ans /= j;
//     }

//     return ans;
// }

int main()
{
    using namespace std;

    int n, a, b;
    cin >> n >> a >> b;
    vec<int> v(n);

    for (auto &e : v)
    {
        cin >> e;
    }

    int countA = count_if(v.cbegin(), v.cend(),
                           [a](int e) {
                               return e <= a;
                           });

    int countB = count_if(v.cbegin(), v.cend(),
                           [b](int e) {
                               return e <= b;
                           }) - countA;

    int countC = n - countA - countB;

    cout << min({countA, countB, countC}) << endl;

    return 0;
}


Measured memory_bytes: 256
a,b,c = map(int,(input().split()))
mb = input()
 
rl = list()
ll = list()
 
for i in range(a):
    if mb[i] == "x":continue
    if len(rl) == 0:
        rl.append(i + 1)
    else:
        if rl[-1] + c + 1 <= i + 1:
            rl.append(i + 1)
            if len(rl) == b:break
 
for i in range(a-1,-1,-1):
    if mb[i] == "x":continue
    if len(ll) == 0:
        ll.append(i + 1)
    else:
        d1 = ll[-1] - c - 1
        d2 = i + 1
        if  d1 >= d2:
            ll.append(i + 1)
            if len(ll) == b:break
 
ans=list()
for i,k in zip(rl,reversed(ll)):
    if b == 1 and len(rl) != 1 or b==0:break
    if i == k:
        ans.append(i)
 
[print(i) for i in ans]

Measured memory_bytes: 23696
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

int top[100][100];
int h[100][100];
int Rotation[4][6]={
	{5,1,4,3,0,2}, //南
	{0,5,2,4,1,3}, //東
	{4,1,5,3,2,0}, //北
	{0,4,2,5,3,1}  //西
};
struct P{int x,y;} d[4]={
{0,-1}, //南
{1,0},  //東
{0,1},  //北
{-1,0}  //西
};

main(){
	int i,j,n,t,f,x,y;
	while(cin>>n,n){
		memset(top, 0, sizeof(top));
		memset(h, 0, sizeof(h));
		while(n--){
			cin >> t >> f;
			int tD[6], D[6]={3,5,4,2,1,6};
			while(D[4] != t || D[0] != f){
				memcpy(tD, D, sizeof(D));
				int r = rand()%4;
				for(i=0;i<6;i++) D[Rotation[r][i]] = tD[i];
			}
			x = 50;
			y = 50;
			while(h[x][y] != 0){
				int dt = 0;
				for(j=6;j>3;j--){
					for(i=0;i<6;i++) if(D[i]==j)break;
//cout << j << " : " << i << " : " << h[x+d[i].x][y+d[i].y] << " : " <<  h[x][y] << endl;
					if(i>=4  || h[x+d[i].x][y+d[i].y] >= h[x][y]) continue;
					dt = i;
					break;
				}
				if(j == 3) break;
				x += d[dt].x;
				y += d[dt].y;
				memcpy(tD, D, sizeof(D));
				for(i=0;i<6;i++) D[Rotation[dt][i]] = tD[i];
			}
			h[x][y] ++;
			top[x][y] = D[4];
//			cout << x << " : " << y << " : " << top[x][y] << " : " << h[x][y] << endl;
		}
		int sum[7]={0};
		for(i=0;i<100;i++)
			for(j=0;j<100;j++)
				sum[top[i][j]] ++;
		cout << sum[1] << ' ' << sum[2] << ' ' << sum[3] << ' ' << sum[4] << ' ' << sum[5] << ' ' << sum[6] << endl;
	}
	return 0;
}

Measured memory_bytes: 0
x,y,z,k = map(int,input().split())	

al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

al = sorted(al)
bl = sorted(bl)
cl = sorted(cl)
rank = []
flag = False
for xx in range(x-1,-1,-1):
    tmp = al[xx]+bl[-1]+cl[-1]
    if flag and rank[-1] >= tmp:
        break
    for yy in range(y-1, -1, -1):
        tmp = al[xx]+bl[yy]+cl[-1]
        if flag and rank[-1] >= tmp:
            break
        for zz in range(z-1,-1,-1):
            if len(rank) < k:
                rank.append(al[xx]+bl[yy]+cl[zz])
                rank = sorted(rank, reverse=True)
            else:
                tmp = al[xx]+bl[yy]+cl[zz]
                if rank[-1] < tmp:
                    flag = True
                    rank.pop()
                    rank.append(tmp)
                    rank = sorted(rank, reverse=True)
                else:
                    break

for i in rank:
    print(i)
                
            
            

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
const int INF=1000000000;

int main(){
    int N;cin>>N;
    int info[N][3];
    rep(i,N)cin>>info[i][0]>>info[i][1]>>info[i][2];
    rep(i,101)rep(j,101){
        int x,y,c;
        rep(k,N){
            if(info[k][2]){
                x=info[k][0];
                y=info[k][1];
                c=info[k][2];
                break;
            }
        }
        int H=c+abs(x-j)+abs(y-i);
        int flag=0;
        rep(k,N){
            if(max(H-abs(info[k][0]-j)-abs(info[k][1]-i),0)!=info[k][2]){
                flag++;
                break;
            }
        }
        if(!flag){
            cout<<j<<" "<<i<<" "<<H<<endl;
            return 0;
        }
    }
    return 0;
}

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

#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define rep(i, st, n) for (int i = (st); i < (n); ++i)
#define repinv(i, st, n) for (int i = ((n)-1); i >= (st); --i)
#define MEM(a, b) memset(a, b, sizeof(a));
#ifdef LOCAL
#define debug(x) std::cerr << #x << ": " << x << endl
#else
#define debug(x) 860111
#endif
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileIO(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

//mt19937 mrand(random_device{}());
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod=1e9+7;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
pii operator+(const pii&x, const pii&y) { return mp(x.X+y.X, x.Y+y.Y);}
pii operator-(const pii&x, const pii&y) { return mp(x.X-y.X, x.Y-y.Y);}
//INT_MAX, ULLONG_MAX, LLONG_MAX or numeric_limits<int>::min()

inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}

//------------------------------------------------------------------------//
int T;
const int maxn = 2e5+7;
int n, k;
//ll a[maxn];

//check T
void solve()
{
  //cin >> n; rep(i, 0, n) cin >> a[i];
  cin >> n >> k;
  //cout << fixed << setprecision(10);
  vector<int> cc(k+1, 0);
  rep(i, 1, n+1)
  {
    int c = i;
    int cnt = 0;
    while(c < k) c = c*2, cnt++;
    //debug(cnt);
    cc[cnt]++;
  }
  double p = 0.0;
  //int id =  0;
  double p2i = 1.0;
  rep(id, 0, k)
  {
    p += 1.0*p2i*cc[id]*(1.0/n);
    //id++;
    p2i/=2.0;
    //debug(p);
  }
  cout << fixed <<  setprecision(20) << p << endl;
  
  return;
}


signed main()
{
  fastIO();
  T = 1;
  //cin >> T; //this
  rep(tc, 1, T+1)
  {
    //cout << "Case #" << tc << ": ";
    solve();
  }
  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
                                                                                                
  
int main(void){
                                                                                                
   
    int a, b, c;
   
      
    scanf("%d %d %d", &a, &b, &c);
   

    if( a == b && b == c && a == c ) printf("1\n");

    else if( a == b ) printf("2\n");

    else if( b == c ) printf("2\n");

    else if( a == c ) printf("2\n");

    else printf("3\n");
   

    return 0;
                                                          
}

Measured memory_bytes: 128
"use strict";

const main = arg => {
    const inputList = arg.trim().split("\n");
    // 回答を記述

    // 回答を記述
    let N = parseInt(inputList[0]);
    const SqrtN = Math.sqrt(N);
    let numList = [] // 素因数分解した後の素数の累乗リスト
    // Nを素因数分解する
    for (let i = 2; i <= SqrtN; i++) {
        let sum = 0;
        while (true) {
            if (N % i !== 0) {
                break;
            }
            N /= i;
            sum++;
        }
        numList.push(sum);
    }

    // √Nまで割って1より大きい=かなり大きい素数のため、素数**1と判定でき、1を追加する
    if (N !== 1) {
        numList.push(1);
    }

    if (numList.length === 0) {
        console.log(0);
    } else {
        let result = 0;
        numList.filter(ele => ele !== 0).forEach(ele => {
            for (let i = 1; i <= ele; i++) {
                ele -= i;
                if (ele < 0) {
                    break;
                }
                result++;
            }
        })

        console.log(result);
    }

}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 65720
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B;cin>>A>>B;
  cout<<"100 100"<<endl;
  vector<string>S(100);

  for(int i=0;i<50;i++)S[i]=string(100,'#');
  for(int i=50;i<100;i++)S[i]=string(100,'.');

  for(int i=0;i<A-1;i++)S[2*(i/50)][(i%50)*2]='.';
  for(int i=0;i<B-1;i++)S[51+2*(i/50)][(i%50)*2]='#';

  for(int i=0;i<100;i++)cout<<S[i]<<endl;
}

/*






*/

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

main(){
  int n, m, s, t;
  cin>> n >> m;
  bool f = true;
  int maxv = m;
  for ( int i = 0; i < n; i++ ){
    cin >> s >> t;
    m = m + s - t;
    if ( m < 0 ) f = false;
    maxv = max(maxv, m);
  }
  if ( !f ) cout << 0 << endl;
  else cout << maxv << endl;

}

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

const int MAXN = 300005, mod = 998244353;

long long n, A, B, K;

int fac[MAXN], ifac[MAXN], inv[MAXN];

int main()
{
	cin >> n >> A >> B >> K;
	fac[0] = 1, ifac[0] = 1, inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = (mod-(long long)mod/i*inv[mod%i]%mod)%mod;
	for (int i = 1; i <= n; i++) {
		fac[i] = (long long)fac[i-1]*i%mod;
		ifac[i] = (long long)ifac[i-1]*inv[i]%mod;
	}
	auto choose = [](int n, int m) {
		return (long long)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
	};
	int ans = 0;
	for (int i = 0; i <= n && K >= A*i; i++) {
		if ((K-A*i)%B != 0) continue;
		int j = (K-A*i)/B;
		if (i <= n && j <= n)
			ans = (ans+(long long)choose(n, i)*choose(n, j))%mod;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3712
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull  unsigned long long
typedef string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int INF = 1e9 + 5;
const int N = 2e5 + 123;
int main(){
    speed;
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    for(int i = 1; i <= (d - b); ++i){
        cout << 'U';
    }
    for(int i = 1; i <= (c - a); ++i){
        cout << 'R';
    }
    for(int i = 1; i <= (d - b); ++i){
        cout << 'D';
    }
    for(int i = 1; i <= (c - a); ++i){
        cout << 'L';
    }
    cout << 'L';
    for(int i = 1; i <= (d - b) + 1; ++i){
        cout << 'U';
    }
    for(int i = 1; i <= (c - a) +1;++i){
        cout << 'R';
    }
    cout << 'D';
    cout << 'R';
    for(int i = 1; i <= (d - b) + 1; ++i){
        cout << 'D';
    }
    for(int i = 1; i <= (c - a) + 1; ++i){
        cout << 'L';
    }
    cout << 'U';
}

Measured memory_bytes: 3552
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define LL long long
using namespace std;
const int N=5005,M=205;
int n,m,x[M][N],h[M][N];
int b[M][N],st[N],w[N];
LL a[N],e[N][N],ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)
		scanf("%lld",&a[i]),a[i]+=a[i-1];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&b[j][i]);
	for(int i=1,p,j;i<=m;i++){
		for(j=1,p=0;j<=n;j++){
			while(p&&w[p]<b[i][j])p--;
			x[i][j]=p?st[p]+1:1;
			st[++p]=j;w[p]=b[i][j];
		}
		for(j=n,p=0;j;j--){
			while(p&&w[p]<b[i][j])p--;
			h[i][j]=p?st[p]-1:n;
			st[++p]=j,w[p]=b[i][j];
		}
		for(j=1;j<=n;j++)
			e[x[i][j]][j]+=b[i][j],
			e[x[i][j]][h[i][j]+1]-=b[i][j],
			e[j+1][j]-=b[i][j],
			e[j+1][h[i][j]+1]+=b[i][j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			e[i][j]+=e[i][j-1];
		for(int j=1;j<=n;j++)
			e[i][j]+=e[i-1][j];
		for(int j=i;j<=n;j++)
			ans=max(ans,e[i][j]-a[j]+a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 208000
N = int(input())
lls = []
rls = []
sels = []
for _ in range(N):
    x,l = map(int, input().split())
    lls.append(x-l)
    rls.append(x+l)
    sels.append([x-l,x+l])

sels = sorted(sels,key=lambda x:x[1])

start = -float('inf')

ans = 0
for item in sels:
    if start <= item[0]:
        ans += 1
        start = item[1]

print(ans)


Measured memory_bytes: 77656
import java.util.Scanner;
class Dice{
	int A,S,D,F,G,H,Z;
	Dice(int a,int s,int d,int f,int g,int h){
		A=a;S=s;D=d;F=f;G=g;H=h;
	}
	void turnN() {
		Z=A;
		A=S;S=H;H=G;G=Z;
	}
	void turnS() {
		Z=A;
		A=G;G=H;H=S;S=Z;
	}
	void turnW() {
		Z=A;
		A=D;D=H;H=F;F=Z;
	}
	void turnE() {
		Z=A;
		A=F;F=H;H=D;D=Z;
	}
	void turnright() {
		Z=S;
		S=F;F=G;G=D;D=Z;
	}
	void turnleft() {
		Z=S;
		S=D;D=G;G=F;F=Z;
	}
}
public class Main{
	public static void main(String args[]) {
		Scanner sc=new Scanner(System.in);
		Dice d=new Dice(sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt());
		int n=sc.nextInt();
		int [] ans=new int [n];
		for(int i=0;i<n;i++) {
			int U=sc.nextInt(),M=sc.nextInt();
			for(int j=0;j<3;j++) {
				d.turnS();
				if(d.A==U)break;
				d.turnE();
				if(d.A==U)break;
			}
			for(int j=0;j<4;j++) {
				d.turnleft();
				if(d.S==M) {
					ans[i]=d.D;
					break;
				}
			}
		}
		for(int i=0;i<n;i++) {
			System.out.println(ans[i]);
		}
		sc.close();
	}
}



Measured memory_bytes: 25912
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int n; cin >> n;
  vector<int> v(n),c(n);
  rep(i,n) cin >> v[i];
  rep(i,n) cin >> c[i];
  vector<tuple<double,int,int,int>> vc;  
  rep(i,n){
    double a = (double)v[i]/(double)c[i];
    vc.emplace_back(a,i,v[i],c[i]);
  }

  sort(vc.begin(),vc.end());
  reverse(vc.begin(),vc.end());

  int ans=0;
  int x = 0,y = 0;
  rep(i,n){
    x+=get<2>(vc[i]);
    y+=get<3>(vc[i]);
    ans = max(x-y,ans);
  }

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


Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>
#include <queue>

using namespace std;




int main()
{
	int H,W,A,B;

	cin >> H >> W >> A >> B;

	vector<vector<int> > table(H, vector<int>(W,0));

	for(int hi = 0; hi < H; hi++){
		for(int wi = 0; wi < W; wi++){
			if(hi < B){
				if (wi < A) table[hi][wi] = 1;
			}else{
				if(wi >= A) table[hi][wi] = 1;
			}
			printf("%d",table[hi][wi]);
		}
		printf("\n");
	}



	return 0;
}



Measured memory_bytes: 5120
"""
重複組み合わせの問題か。
Sに仕切りを入れて、考える。
1個仕切りを入れる場合、

仕切りの数×3個を排除して置く。
"""
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


S = int(input())
if S <= 2:
    print(0)
    exit()
ans = 0
for i in range(S):
    n = S-(i+1)*3
    ans += cmb(n+i,i,p)
    ans %= p
print(ans)

Measured memory_bytes: 167836
N = int(input())
mod = 1000000007

primes = list()

for i in range(2, N+1):
    for j in primes:
        if i % j == 0:
            break
    else:
        primes.append(i)

ans = 1
for p in primes:
    x = 1
    q = p
    while q <= N:
        for i in range(2, N+1):
            if i % q == 0:
                x += 1
        q *= p
    ans = ans * x % mod

print(ans)


Measured memory_bytes: 3060
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000000;
const int mod = 1000000007;
const int INF = 1 << 30;
#define rep(i,n) for(ll i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
#define pp pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define fix(n) fixed<<setprecision(n)
#define itr vector<ll>::iterator
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
string YN(bool b) { return(b ? "YES" : "NO"); }
string yn(bool b) { return(b ? "Yes" : "No"); }
ll a, b;
int main() {
	cin >> a >> b;
	cout << b * 2 - a << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <iostream>


using namespace std;

//FILE *in = freopen("input.txt", "r", stdin);

enum{
	MAX_X = 30,
	MAX_Y = 30
};

int g_cost[MAX_X][MAX_Y][4];
int g_table[MAX_X][MAX_Y];
int g_opCost[4];

struct State{
	State(int x, int y, int cost, int dir) : x(x), y(y), cost(cost), dir(dir){}
	bool operator< (State & other){
		return cost > other.cost;
	}
	bool operator< (const State & other) const{
		return cost > other.cost;
	}
	int x;
	int y;
	int cost;
	int dir;
};

//右　下　左　上
int dirX[4] = {1, 0, -1, 0};
int dirY[4] = {0, 1, 0, -1};

int OPedDir(int op, int oldDir){
	return (oldDir + op)%4;
}

int solution(int w, int h){

	priority_queue<State> que;
	vector<State> states;
	State current(0,0,0,0);
	states.push_back(current);
	g_cost[0][0][0] = 0;

	while(true){
		while(true){
			int op = g_table[current.x][current.y];
			if(op==4){ // 止まったら
				if(current.x==w-1 && current.y==h-1) return current.cost;
				break;
			}
			
			int dir = OPedDir(op, current.dir);
			int x = current.x + dirX[dir];
			int y = current.y + dirY[dir];
		
			if(x<0 || y<0 || x>=w || y>=h) break;
			if(g_cost[x][y][dir] <= current.cost) break;
			g_cost[x][y][dir] = current.cost;
			current.x = x;
			current.y = y;
			current.dir = dir;
			
			states.push_back(current);
		}
		for(auto it=states.begin(); it!=states.end(); it++){
			for(int op=0; op<4; op++){
				int dir = OPedDir(op, it->dir);
				int x = it->x + dirX[dir];
				int y = it->y + dirY[dir];
				if(x<0 || y<0 || x>=w || y>=h) continue;
				if(g_cost[x][y][dir] <= it->cost + g_opCost[op]) continue;
				g_cost[x][y][dir] = it->cost + g_opCost[op];
				que.emplace(x, y, g_cost[x][y][dir], dir);
			}
		}
		states.clear();
		current = que.top();
		states.push_back(current);
		que.pop();
	}
}

int main() {
	int w, h;
	while(true){
		cin >> w;
		cin >> h;
		if(w==0 && h==0) break;
		
		fill(&g_cost[0][0][0], &g_cost[w][h][4], 30000);
		for(int y=0; y<h; y++){
			for(int x=0; x<w; x++){
				int op;
				cin >> op;
				g_table[x][y] = op;
			}
		}
		for(int i=0; i<4; i++){
			int cost;
			cin >> cost;
			g_opCost[i] = cost;
		}
		cout << solution(w,h) << endl;
	}
	return 0;
}

Measured memory_bytes: 1344
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int N;
  int t, x, y;
  int t_b, x_b, y_b;
  int t_d, x_d, y_d;
  int i;
  int able;
  
  scanf("%d", &N);
  
  t_b = 0;
  x_b = 0;
  y_b = 0;
  able = 1;
  for(i = 0; i < N; i++){
    scanf("%d %d %d",&t,&x,&y);
    t_d = t - t_b;
    x_d = x - x_b;
    y_d = y - y_b;
    if(t_d >= x_d + y_d && abs((x_d + y_d)) % 2 == t_d % 2){
      t_b = t;
      x_b = x;
      y_b = y;
    }else{
      able = 0;
    }
  }
  
  // 出力
  if(able == 1){
    printf("Yes\n");
  }else{
    printf("No\n");
  }

  return 0;
}

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

int main(){
    long long N,K;
    cin>>N>>K;
    double res=0.0;
    for(long long n=1;n<=N;n++){
        double tmp=1.0;
        long long nn=n;
        while(nn<K) nn*=2,tmp/=2.0;
        res+=tmp;
    }
    res/=N;
    cout<<fixed<<setprecision(10)<<res<<endl;
}

Measured memory_bytes: 256
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

int main() {
  int m, n;
  scanf("%d%d", &m, &n);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  int ret = a[n - 1] - a[0];
  for (int i = 1; i < n; ++i) {
    ret = min(ret, a[i - 1] + m - a[i]);
  }
  printf("%d\n", ret);
  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>

int main(){
    
    char arr[105];
    scanf("%[^\n]", arr);
    
    arr[0] = '2';
    arr[1] = '0';
    arr[2] = '1';
    arr[3] = '8';
    
    printf("%s\n", arr);
    
    return 0;
}

Measured memory_bytes: 1580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define double long double
typedef pair<double, int> P;

struct edge {
	int to;
	double cost;
};

double x[1010];
double y[1010];
double r[1010];
double d[1010];

vector<edge> G[1010];

double dist(int i, int j) {
	double dx = x[i] - x[j];
	double dy = y[i] - y[j];
	double d = sqrt(dx * dx + dy * dy);
	if(d < r[i] + r[j]) return 0;
	return d - (r[i] + r[j]);
}

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

	double xs, ys, xt, yt;
	int N;
	cin >> xs >> ys >> xt >> yt >> N;

	for(int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> r[i];
	}
	x[N] = xs, y[N] = ys, r[N] = 0;
	x[N + 1] = xt, y[N + 1] = yt, r[N + 1] = 0;

	for(int i = 0; i < N + 2; i++) {
		for(int j = 0; j < N + 2; j++) {
			if(i == j) continue;
			G[i].push_back(edge{ j, dist(i, j) });
		}
	}

	fill(d, d + N + 2, 1e20);
	d[N] = 0;
	priority_queue <P, vector<P>, greater<P>> q;
	q.push(P(0, N));
	while(q.size()) {
		int v = q.top().second;
		double c = q.top().first;
		q.pop();
		if(d[v] < c) continue;
		for(auto e : G[v]) {
			if(d[e.to] >  c + e.cost) {
				d[e.to] = c + e.cost;
				q.push(P(d[e.to], e.to));
			}
		}
	}
	cout << fixed << setprecision(15) << d[N + 1] << endl;
}

Measured memory_bytes: 40812
#include<iostream>
#include<string>
#include<algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <map>

using namespace std;
typedef int status;
typedef long long LL;
const int INF = int(1e9);
const int MAX = 100005;

struct S
{
    int x,wei;
}A[MAX],B[MAX];

struct Bian
{
    int x,y;
    int len;
}biao[MAX*10];
int num = 0;

bool cmp(S a,S b)
{
    return a.x<b.x;
}

bool cmp1(Bian a,Bian b)
{
    return a.len<b.len;
}

int N;

int visit[MAX] = {0};

int Find(int x)
{
    if(visit[x]==x)
        return x;
    else
        return visit[x] = Find(visit[x]);
}

int mix(int x,int y)
{
    int Tx = Find(x);
    int Ty = Find(y);
    if(Tx!=Ty)
    {
        visit[Tx] = Ty;
        return 1;
    }
    return 0;

}


int main()
{
    cin>>N;
    for(int i = 1;i<=N;i++)
    {
        A[i].wei = B[i].wei = i;
        scanf("%d %d",&A[i].x,&B[i].x);
    }
    sort(A+1,A+1+N,cmp);sort(B+1,B+1+N,cmp);
    for(int i = 1;i <N;i++)
    {
        biao[num].x = A[i].wei;
        biao[num].y = A[i+1].wei;
        biao[num++].len = A[i+1].x - A[i].x;
        biao[num].x = B[i].wei;
        biao[num].y = B[i+1].wei;
        biao[num++].len = B[i+1].x - B[i].x;
    }
    sort(biao,biao+num,cmp1);

    LL sum = 0;
    for(int i = 0;i<=N;i++)
        visit[i] = i;
    for(int i = 0;i<num;i++)
    {
        Bian temp = biao[i];
        if(mix(temp.x,temp.y)==1)
        {
            sum += temp.len;
        }
    }

    cout<<sum<<endl;

    return 0;
}


Measured memory_bytes: 7808
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

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

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n,m;
	cin >> n >> m;
	vector<vector<int> > edge(n);

	for(int i = 0; i < m; i++){
		int x,y;
		cin >> x >> y;
		x--;
		y--;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}

	vector<bool> node(n);
	bool flag = false;
	for(int i = 0; i < edge[0].size(); i++){
		node[edge[0][i]] = true;
	}
	for(int i = 0; i < edge[n-1].size(); i++){
		if(node[edge[n-1][i]]) flag = true;
	}
	if(flag) cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;


	return 0;
}

Measured memory_bytes: 12016
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for _ in range(N)]

sum_money = float("inf")
for i in range(2 ** N):
  money = 0
  algorithm = [0]*M
  for j in range(N):
    if (i >> j) & 1 == 1:
      money += CA[j][0]
      for k in range(M):
        algorithm[k] += CA[j][k+1]
  check = True
  for l in algorithm:
    if l < X:
      check = False
  if check:
    sum_money = min(sum_money, money)
    
print(sum_money if sum_money != float("inf") else -1)

Measured memory_bytes: 9220
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



ll n,a,b,c,d;
map<ll,ll> dp;
ll solve(ll n) {
	if (dp.count(n)) return dp[n];
	ll ans = 4e18, t;
	REP(u,-1,1) if (n+u>=0&&(n+u)%2==0) { 
		t = solve((n+u)/2);
		ans = min(ans,t+a+abs(u)*d);
		if (n/2<=(ans-t-abs(u)*d)/d) ans=t+n/2*d+abs(u)*d;
	}
	REP(u,-2,2) if (n+u>=0&&(n+u)%3==0) {
		t = solve((n+u)/3);
		ans=min(ans,t+b+abs(u)*d);
		if (2*n/3<=(ans-t-abs(u)*d)/d) ans=t+2*n/3*d+abs(u)*d;
	}
	REP(u,-4,4) if (n+u>=0&&(n+u)%5==0) {
		t = solve((n+u)/5);
		ans=min(ans,t+c+abs(u)*d);
		if (4*n/5<=(ans-t-abs(u)*d)/d) ans=t+4*n/5*d+abs(u)*d;
	}
	return dp[n]=ans;
}

void work() {
	dp.clear();
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	dp[0] = 0, dp[1] = d;
	printf("%lld\n",solve(n));
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) work();
}









Measured memory_bytes: 4596
N_n_osatsu, Y_sum_money = map(int, input().split())

rest_money = Y_sum_money
rest_n_osatsu = N_n_osatsu
n_each_osatsu_list = [] # 万札、五千円札、千円札の枚数の2重リスト

def skip_search(rest_money, rest_n_osatsu):  # 明らかに無理な場合、処理をスキップ。これを入れないと制限時間超過
    if rest_n_osatsu*1000 > rest_money or rest_n_osatsu*10000 < rest_money:
        return True

for n_10000 in range(int(Y_sum_money/10000 +1)): # 万札枚数。0枚からスタート
    rest_money = Y_sum_money - 10000*n_10000
    rest_n_osatsu = N_n_osatsu - n_10000
    if skip_search(rest_money, rest_n_osatsu):
        break

    if rest_money == 0: # 万札だけで目標金額になる場合
        n_each_osatsu_list.append([n_10000, 0, 0])
        break

    for n_5000 in range(int(rest_money/5000 + 1)): # 万札枚数決定後に5000円の枚数を探索。5000円0枚からスタート
        rest_money = Y_sum_money - 10000*n_10000 - 5000*n_5000
        rest_n_osatsu = N_n_osatsu - n_10000 - n_5000
        if skip_search(rest_money, rest_n_osatsu):
            break
        n_1000 = int(rest_money/1000)
        n_each_osatsu_list.append([n_10000, n_5000, n_1000])

n_sum_osatsu_list = [sum(x) for x in n_each_osatsu_list] # お札合計枚数のリスト

try:
    print(*n_each_osatsu_list[n_sum_osatsu_list.index(N_n_osatsu)], sep=" ")
except:
    print("-1 -1 -1")

Measured memory_bytes: 95340
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define INF 2e9
#define MOD (1000000007)
#define EPS 1e-9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long long int lli;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<pair<string, pair<int, int>>> a(N);
    REP(i, N)
    {
        cin >> a[i].first >> a[i].second.first;
        a[i].second.first *= -1;
        a[i].second.second = i;
    }
    sort(a.begin(), a.begin() + N);
    for (int i = 0; i < N; i++)
    {
        /*        cout << a[i].first
             << " " << a[i].second.first
             << " " << a[i].second.second << "\n";*/
        cout << a[i].second.second + 1 << "\n";
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 1000 + 15
using namespace std;
bool check[MAXN];
int a[MAXN], k;
int e[MAXN];
const int mod = 1e9 + 7;

void put_prime() {
    for(int i = 2; i <= MAXN; i++) {
        if(!check[i]) {
            a[k++] = i;
            for(int j = 1; i * j <= MAXN; j++)
                check[i*j] = true;
        }
    }
}

void add_integer(int n) {
    for(int i = 0; i < k; i++) {
        while(n % a[i] == 0) {
            e[a[i]]++;
            n /= a[i];
        }
        if(n == 1)  break;
    }
}

int main () {
    int n;
    long long ans = 1;
    scanf("%d", &n);
    put_prime();
    for(int i = 2; i <= n; i++)
        add_integer(i);
    for(int i = 2; i <= n; i++)
        if(e[i]) ans = (ans * (e[i] + 1)) % mod;
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 128
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++){
		    a[i] = sc.nextInt();
		}
		
		// 計算
		int[] result = new int[n];
		for(int i = 0; i < n; i++){
		    if(i%2 == 0){
		        result[0] += a[i];
		    }else{
		        result[0] += -a[i];
		    }
		}
		
		for(int i = 1; i < n; i++){
		    result[i] = 2*a[i-1] - result[i-1];
		}
		
		// 出力
		for(int i = 0; i < n; i++){
		    System.out.print(result[i] + " ");
		}
		
	}
}


Measured memory_bytes: 64824
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()

	n := readInt()
	i := 0
	for (i+1)*(i+1) <= n {
		i++
	}
	println(i * i)
}


Measured memory_bytes: 640
import java.io.*;
import java.lang.*;
import java.util.*;

class Main
{
	public static void main(String args[])throws IOException
	{
		FastReader scn = new FastReader();
		int N = scn.nextInt();

		long[] MINUS = new long[N];
		long[] PLUS = new long[N];

		for(int i = 0; i < N; i++)
		{
			long x  = scn.nextLong();
			long y = scn.nextLong();

			MINUS[i] = x - y;
			PLUS[i] = x + y;
		}	
		
		Arrays.sort(MINUS);
		Arrays.sort(PLUS);

		System.out.println(Math.max( Math.abs(PLUS[N-1] - PLUS[0]), Math.abs(MINUS[N-1] - MINUS[0]) ));

	}

	public static long nCr(long n, long k, long M)
	{
		long num_factorial = 1;
		for(long i = n + k - 1; i >= n; i--)
		{
			num_factorial = (num_factorial * i)%M;
		}
		//System.out.println(num_factorial);
		long denom_factorial = 1;
		for(long i = k; i > 0; i--)
			denom_factorial = (denom_factorial * getInverseModulo(i, M))%M;

		//System.out.println(denom_factorial);

		return (num_factorial * denom_factorial)%M;
	}

	public static long getPowerModulo(long a, long p, long m)
    {   
        if(p==0)
            return 1;
 
        long temp = getPowerModulo(a, p/2, m);
        temp = (temp * temp)%m;
        if(p%2 == 0)
            return temp;
        else
            return (a * temp)%m;
 
    }

    public static long getInverseModulo(long a, long P)
    {
        return getPowerModulo(a, P-2, P);
    }

	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 (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 (IOException e) 
            {
                e.printStackTrace(); 
            }
            return str; 
        } 
    }
}

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

int main(){
  int n;
  cin >> n;
  vector<int> l(n);
  for(int i=0; i<n; i++) cin >> l[i];
  sort(l.begin(),l.end()); reverse(l.begin(),l.end());
  int count = 0;
  for(int i=0;i<n;i++){
    for(int j=i+1; j<n; j++){
      for(int k=j+1; k<n; k++){
        if(l[i] < l[j] + l[k]) count++;
        else break;
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 384