akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		int M = scn.nextInt();
		Ship[] S = new Ship[M];
		for(int i = 0;i < M;i++) {
			S[i] = new Ship(scn.nextInt(), scn.nextInt());
		}
		Arrays.sort(S);

		boolean[] Go = new boolean[N];
		for(int i = 0;i < M;i++) {
			if(S[i].getA() == 1) {
				Go[S[i].getB()-1] = true;
			}
			if(S[i].getB()==N) {
				if(Go[S[i].getA()-1])Go[N-1] = true;
			}
			if(Go[N-1])break;
		}


		System.out.println(Go[N-1]?"POSSIBLE":"IMPOSSIBLE");
	}

}

class Ship implements Comparable<Ship>{
	int a;
	int b;

	Ship(int a, int b){
		this.a = a;
		this.b = b;
	}

	@Override
	public int compareTo(Ship o) {
		if(this.a > o.getA())return 1;
		if(this.a < o.getA())return -1;
		return 0;
	}

	public int getA() {
		return a;
	}
	public int getB() {
		return b;
	}

}


Measured memory_bytes: 106484
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;

int main(int argc, const char * argv[]) {
	int s;
	cin >> s;
	REP(i,300){
//		printf("%d : %d",i+1,s);
		if(s==1||s==2||s==4) {println(i+4)break;}
//		cout << endl;
		if(s%2==0){
			s/=2;
		}else{
			s = s*3+1;
		}
	}
}


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

int main(){
  int ans;
  ans = 0;
  int r, g, b, N;
  cin >> r >> g >>  b >> N;
  
  for(int i = 0; i * r <= N; i++){
    for(int j = 0; j * g <= N - i*r; j++){
      if((N - i*r - j*g) % b == 0)ans++;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll  long long  
#define pb push_back
#define fi first
#define se second
using namespace std;
//vector<ll> v[1000001];
void dfs(ll u,ll p)
{
	
}
bool comp(const pair<ll,ll>&a,const pair<ll,ll> &b)
{
	return (a.second < b.second);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 int tc=1;
//cin>>tc;
ll cas=1;
 while(tc--)
 {
	ll s,w;
	cin>>s>>w;
	if(w>=s)
	cout<<"unsafe";
	else
	cout<<"safe";
	cout<<"\n"; 
 } 
}


Measured memory_bytes: 3660
<?php
list($c[]) = strs();
list($c[]) = strs();
echo $c[0][0] === $c[1][2] && $c[0][1] === $c[1][1] && $c[0][2] === $c[1][0] ? 'YES' : 'NO';
function strs()
{
    return explode(' ', trim(fgets(STDIN)));
}


Measured memory_bytes: 4728
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

bool check(char c)
{
    if (c == 'A' || c == 'G' || c == 'C' || c == 'T') 
        return true;
    return false;
}

int str(string &s)
{
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (check(s[i])) {
            int tmp = 1;
            for (int j = i+1; j < s.length(); ++j) {
                if (check(s[j])) ++tmp;
                else break;
            }
            if (ans < tmp) ans = tmp;
        }
    }
    return ans;
}

int main()
{
    string s;
    cin >> s;
    printf("%d\n", str(s));

    return 0;
}

Measured memory_bytes: 256
# encoding: utf-8


import sys
import math

_input = sys.stdin.readlines()
depth = int(_input[0])
sin_60, cos_60 = math.sin(math.pi / 3), math.cos(math.pi / 3)


class Point(object):
    def __init__(self, x=0.0, y=0.0):
        """
        initialize the point
        """
        self.x = float(x)
        self.y = float(y)


def koch_curve(d, p1, p2):
    if not d:
        # print('end')
        return None

    # why can't it be like below?
    # s, t, u = Point(), Point, Point()
    s, t, u = (Point() for _ in range(3))

    s.x = (2 * p1.x + p2.x) / 3
    s.y = (2 * p1.y + p2.y) / 3

    t.x = (p1.x + 2 * p2.x) / 3
    t.y = (p1.y + 2 * p2.y) / 3

    u.x = (t.x - s.x) * cos_60 - (t.y - s.y) * sin_60 + s.x
    u.y = (t.x - s.x) * sin_60 + (t.y - s.y) * cos_60 + s.y

    koch_curve(d - 1, p1, s)
    print(format(s.x, '.8f'), format(s.y, '.8f'))

    koch_curve(d - 1, s, u)
    print(format(u.x, '.8f'), format(u.y, '.8f'))

    koch_curve(d - 1, u, t)
    print(format(t.x, '.8f'), format(t.y, '.8f'))

    koch_curve(d - 1, t, p2)


if __name__ == '__main__':
    p1_start, p2_end = Point(x=0, y=0), Point(x=100, y=0)
    print(format(p1_start.x, '.8f'), '', format(p1_start.y, '.8f'))
    koch_curve(depth, p1_start, p2_end)
    print(format(p2_end.x, '.8f'), '', format(p2_end.y, '.8f'))

Measured memory_bytes: 8100
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll n,t;
  cin>>n>>t;

  ll z[n];
  for(ll i=0;i<n;i++){
    cin>>z[i];
  }

  ll ans=t;
  for(ll i=1;i<n;i++){
    if(z[i]-z[i-1]<t) ans+=z[i]-z[i-1];
    else ans+=t;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1792
package main

import "fmt"


func main() {
	var x, y int
  	fmt.Scan(&x, &y)
  
  if 4*x >= y && 2*x <= y && y % 2 == 0 {
  	 if (y-2*x) % 2 == 0 || (4*x-y) % 2 == 0 {
      fmt.Println("Yes")
    }
  }else {
      fmt.Println("No")
  }
}

Measured memory_bytes: 1756
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ll = long long;

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

  ll cnt = 0;
  ll min_p = 2 * 1e5 + 1;
  REP(i, 0, N) {
    ll p; cin >> p;

    if (p <= min_p) {
      cnt++;
      min_p = p;
    }
  }

  cout << cnt << endl;
}


Measured memory_bytes: 256
/********************************************************************************
	
	Code by a weak man who named CYJian, and he hopes the code can get more points.

	Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define ra read_alpha()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline char read_alpha() { char c = ge; while(!isalpha(c) && c != EOF) c = ge; return c; }
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

#define ERROR return puts("No"), 0
#define OK return puts("Yes"), 0

const int MAXN = 100010;

vector<int>to[MAXN];
int vis[MAXN];
int A, B;

inline void dfs(int x) {
	vis[x] = 1;
	for(auto u : to[x])
		if(vis[u] == 2) A ? B = u : A = u;
		else if(!vis[u]) dfs(u);
}

int main() {
#ifdef LOCAL
	FILE("");
#endif
	int n = ri, m = ri, mxd = 0, mxc = 0;
	for(int i = 1; i <= m; i++) {
		int u = ri, v = ri;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)
		if(to[i].size() & 1) ERROR;
		else if(to[i].size() > mxd) mxd = to[i].size(), mxc = 1;
		else mxc += mxd == to[i].size();
	if(mxd >= 6) OK;
	else if(mxd == 2 || mxc == 1) ERROR;
	else if(mxc > 2) OK;
	else {
		int cnt = 0;
		for(int i = 1; i <= n; i++)
			if(to[i].size() == 4)
				vis[i] = 2;
		for(int i = 1; i <= n; i++)
			if(!vis[i]) A = B = 0, dfs(i), cnt += A == B;
		puts(cnt ? "Yes" : "No");
	}
	return 0;
}

Measured memory_bytes: 6784
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0; i<n; i++){
    cin>>a.at(i);
  }
  sort(a.begin(),a.end(),greater<int>());
  int Alice=0,Bob=0;
  for(int i=0; i<n; i++){
    if(i%2==0) Alice+=a.at(i);
    else Bob+=a.at(i);
  }
  cout<<Alice-Bob<<endl;
}


Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        if (n == 1) {
            System.out.println(1);
            return;
        }
        for (int i = 1; i <= n; i++) {
            long sum = i * (i + 1) / 2;
            if (sum <= n) {
                continue;
            }
            for (int j = 1; j <= i; j++) {
                if (j == sum - n) {
                    continue;
                }
                System.out.println(j);
            }
            break;
        }
    }

}


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

using namespace std;

int my_max(int a, int b) {
    return a > b ? a : b;
}

int my_abs(int x) {
    return x < 0 ? -x : x;
}

int main() {

    int n, m;
    cin >> n >> m;

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

    for(int i=0; i<m; i++) {
        n -= a[i];
        if(n < 0) {
            cout << "-1" << endl;
            return 0;
        }
    }


    cout << n << endl;

    return 0;
}


Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main()
{
    long long n,m;
    cin >> n >> m;
    long long H[n];
    for(long long i=0;i<n;i++)
        cin >> H[i];
        
        long long arr[m][2];
        for(long long i=0;i<m;i++)
            cin >> arr[i][0] >> arr[i][1];
            int arr1[n];
            for(long long i=0;i<n;i++)
                arr1[i]=-1;
            for(long long i=0;i<m;i++)
            {
                if(H[arr[i][0]-1]>H[arr[i][1]-1]&&arr1[arr[i][0]-1]!=0)
                    arr1[arr[i][0]-1]=1;
                    else
                        arr1[arr[i][0]-1]=0;
                    
                    if(H[arr[i][0]-1]<H[arr[i][1]-1]&&arr1[arr[i][1]-1]!=0)
                    arr1[arr[i][1]-1]=1;
                    else
                        arr1[arr[i][1]-1]=0;
            }
            long long count=0;
            for(long long i=0;i<n;i++)
            {
                if(arr1[i]==1||arr1[i]==-1)
                    count++;
            }
            cout << count;
            return 0;
}

Measured memory_bytes: 6348
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    int n = s.length();
    int cnt = 0;
    for (int i = 0; i + 1 < n; ++i) {
        if (s[i] != s[i + 1]) {
            ++cnt;
        }
    }

    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    if (cnt == 0) {
        cout << 1 << '\n';
        return 0;
    }
    if (n == 2) {
        cout << 2 << '\n';
        return 0;
    }
    if (n == 3) {
        set<string> S;
        S.insert(s);
        queue<string> que;
        que.push(s);
        while (!que.empty()) {
            string s = que.front();
            que.pop();

            for (int i = 0; i + 1 < n; ++i) {
                if (s[i] != s[i + 1]) {
                    auto t = s;
                    t[i] = t[i + 1] = 'a' + 'b' + 'c' - t[i] - t[i + 1];
                    if (S.count(t) == 0) {
                        S.insert(t);
                        que.push(t);
                    }
                }
            }
        }

        cout << S.size() << '\n';
        return 0;
    }

    const long long MOD = 998244353;

    vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(3, vector<long long>(3, 0)));
    auto ndp = dp;
    dp[0][0][0] = dp[0][1][1] = dp[0][2][2] = 1;
    for (int _ = 1; _ < n; ++_) {
        for (auto& VV : ndp) {
            for (auto& V : VV) {
                fill(V.begin(), V.end(), 0);
            }
        }

        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                for (int k = 0; k < 3; ++k) {
                    if (dp[i][j][k] == 0) {
                        continue;
                    }

                    for (int l = 0; l < 3; ++l) {
                        int ni = i, nj = j, nk = l;
                        nj = (nj + l) % 3;
                        if (k == l) {
                            ni = 1;
                        }

                        (ndp[ni][nj][nk] += dp[i][j][k]) %= MOD;
                    }
                }
            }
        }
        swap(ndp, dp);
    }

    long long res = 0;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'b') {
            sum += 1;
        } else if (s[i] == 'c') {
            sum += 2;
        }
    }
    sum %= 3;
    for (int i = 0; i < 3; ++i) {
        res += dp[1][sum][i];
    }
    if (cnt == n - 1) {
        ++res;
    }
    res %= MOD;

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 720
X = int(input())
result_list = [0]*100200
result_list[0] = 1
a = [i for i in range(100,106)]
for i in range(100001):
    if result_list[i] == 1:
        for j in a:
            result_list[i+j] = 1
print(result_list[X])

Measured memory_bytes: 3828
n,m=map(int,input().split())
List=sorted(list(map(int,input().split())))
s=[]
for _ in range(m):
    s.append(list(map(int,input().split())))
s.sort(key=lambda x: x[1], reverse=True)

ans=0
j=0
for i in range(m):
    if j>=n or s[i][1]<=List[j]:
        break
    while j<n and s[i][0]>0 and s[i][1]> List[j]:
        ans+=s[i][1]
        s[i][0]-=1
        j+=1
if j>=n:
    print(ans)
else:
    print(ans+sum(List[j:]))


Measured memory_bytes: 32860
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;

int main(){
  IOS();
  ll n,m;
  cin >> n >> m;
  if (m < 2*n) return cout << m/2 << endl,0;
  m -= 2*n;
  cout << n + m/4 << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    int cnt = 0;
    for(int i = 0; i < N-1; i++){
        if(S[i] != S[i+1]) cnt++;
    }
    int ans = N-cnt+(2*K)-1;
    ans = min(ans, N-1);
    cout << ans << endl;
}

Measured memory_bytes: 888
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<iomanip>

#define mod 1000000007
#define ll long long int
#define pb(x) push_back(x)
#define MP(x,y) make_pair(x,y)

using namespace std;

ll power(ll a, ll b, ll m)
{
	if (b == 0)
		return(1);
	ll sol = power(a, b / 2, m);
	sol = (sol * sol) % m;
	if (b % 2 == 1)
		sol = (sol * a) % m;
	return(sol);
}

ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	else
	{
		return gcd(b, a % b);
	}
}
vector<char>v;
void solve()
{
	int n;
	char a;
	cin >> n;
	cin >> a;
	v.pb(a);
	for (int i = 1; i < n; i++)
	{
		cin >> a;
		if (a != v.back())
			v.pb(a);
	}
	cout << v.size();
}
int main()
{
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();
        int[][] X = new int[N+1][D+1];

        int c = 0;
        int m = 0 ;
        double sqrt = 0;

        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= D; j++){
                X[i][j] = sc.nextInt();
            }
        }

        for(int i = 1; i <= N -1; i++){
           for(int j = i +1; j <= N; j++){
            //    if(i == j){
            //         break;
            //    }
               for(int k = 1; k <= D; k++){
                    m += (X[i][k]-X[j][k]) * (X[i][k]-X[j][k]);
               }  

                sqrt = Math.sqrt(m);
                if(sqrt == (int)sqrt){
                    c++;
                }
                
                m = 0;
            }
        }


        System.out.println(c);
        
    }

}

Measured memory_bytes: 21716
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <sstream>
#include <stdio.h>
using namespace std;

// Reverse Sequence(0006)
int main()
{
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
int GCD(int a, int b){
  return b?GCD(b,a%b):a;
}
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  vector<int> l(n+1,0),r(n+1,0);
  for(int i=0;i<n;i++){
    l[i+1]=GCD(a[i],l[i]);
    r[n-1-i]=GCD(a[n-1-i],r[n-i]);
  }
  int ans=1;
  for(int i=0;i<n;i++){
    if(ans<GCD(l[i],r[i+1]))ans=GCD(l[i],r[i+1]);
  }
  cout << ans << endl;
}

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

int main() {
  int a[101], m, x, y;
  bool b;
  m = 0;
  memset(a, 0, sizeof(int)*101);
  while (cin >> x >> y) {
    if (!x && !y) {
      if (a[1]&1 && a[2]&1) {
        b = true;
        for (int i=3; i<=m; i++) {
          if (a[i]&1) {
            b = false;
            break;
          }
        }
      } else {
        b = false;
      }
      if (b) cout << "OK" << endl;
      else cout << "NG" << endl;
      m = 0;
      memset(a, 0, sizeof(int)*101);
    } else {
      m = max(m, max(x, y));
      ++a[x];
      ++a[y];
    }
  }
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    string N;
    cin>>N;
    bool check=false;
    for(ll i=0;i<N.length();i++){
        if(N[i]=='7'){
            check=true;
            break;
        }
    }
    if(check) cout<<"Yes";
    else cout<<"No";
}
    

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a, b) accumulate(all(a), b)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
ll const INF = 1e18;

template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for(auto& i : v) cin >> i;
    REP(i, n){
        int c;
        cin >> c;
        v[i] = max(0, v[i] - c);
    }
    cout << SUM(v, 0) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int           long long
#define	pb            push_back
#define all(a)        (a).begin(),(a).ant()
#define sz(x)         (int)x.size()
#define F             first
#define S             second
#define endl          "\n"
#define inf           1000000007
#define FOR(i, a, b)  for(int i=a; i<b; i++)
#define bigboi        1e18
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(aint(v), RNG);
// Use mt19937_64 for 64 bit random numbers. 

vector<int> adj[100005], vis(100005), mark(100005), arr(100005);

void dfs(int u, int p=-1){
	vis[u] = 1;
	int k = 0;
	for(int v:adj[u]){
		k = max(k, arr[v]);
		if(!vis[v] && v!=p){
			dfs(v, u);
		}
	}
	if(k<arr[u]){
		mark[u] = 1;
	}
}
void solve(){
	int n, m, cnt=0;
	cin>>n>>m;
	FOR(i, 1, n+1) cin>>arr[i];
	while(m--){
		int a, b;
		cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	FOR(i, 1, n+1){
		dfs(i);
	}
	FOR(i, 1, n+1){
		//cout<<mark[i]<<' ';
		cnt+=(mark[i]==1);
	}
	cout<<cnt<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); 	
	int t=1;
	//cin>>t;
	FOR(i, 1, t+1){		
	//	cout<<"Case #"<<i<<":"<<endl;
		solve();
	}
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
 
}


Measured memory_bytes: 13012
#include <cstdio>
#define FOR(i, l, r) for(int i = l; i <= r; ++i)

using namespace std;

#define left LEFT
typedef long long ll;
const int N = 510;
const int mod = 1e9 + 7;

int n, k, ans, tot, left, a[N], c[N][N];
char s[N];

bool check()
{
    if (!tot) return 0;
    int now1 = 1, now2 = 1, c = 0;
    FOR(i, 1, k)
    {
        if (!(now1 <= tot || a[now2] > 1 || c)) break;
        if (now1 <= tot && s[i] == 'r') ++now1; else
        if (now2 < now1 && a[now2] > 1 && s[i] == 'b') c += a[now2++] - 2;
        else if (c) --c;
    }
    return !(now1 <= tot || a[now2] > 1 || c);
}

void update()
{
    ll tmp = 1, num = tot + 1;
    for(int i = 1, j; i <= tot; i = j + 1)
    {
        for(j = i; a[j + 1] == a[i]; ++j);
        tmp = tmp * c[j][i - 1] % mod;
        num += (j - i + 1) * (a[i] * 2 - 1);
    }
    tmp = tmp * c[num + left - 1][num - 1] % mod;
    if ((ans += tmp) >= mod) ans -= mod;
}

void dfs(int mx)
{
    if (left < 0) return;
    if (check()) update();

    if (tot) --left;
    ++tot; --left; dfs(a[tot] = 1); ++left;
    FOR(i, 2, mx)
    {
        left -= i * 2 - 3;
        dfs(a[tot] = i);
        left += i * 2 - 3;
    }
    a[tot--] = 0;
    if (tot) ++left;
}

int main()
{
    FOR(i, 0, 500)
    {
        c[i][0] = 1;
        FOR(j, 1, 500)
            if ((c[i][j] = c[i - 1][j] + c[i - 1][j - 1]) >= mod)
                c[i][j] -= mod;
    }

    scanf("%d%d%s", &n, &k, s + 1);
    left = n; dfs(100);
    printf("%d\n", (ans + 1) % mod);
    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> dam(N);
  for (int i = 0; i < N; i++){
    cin >> dam.at(i);
  }
  vector<int> yama(N);
  yama.at(0) = 0;
  for (int i=0;i<N;i++){
    if(i%2==1){
      yama.at(0) -= dam.at(i);
    }else{
      yama.at(0) += dam.at(i);
    }
  }
  for (int i=1;i<N;i++){
    yama.at(i) = 2 * dam.at(i-1) - yama.at(i-1);
  }
  for (int i=0; i<N ; i++){
    cout << yama.at(i) << " ";
  }
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#include <bitset>
#define M 1000000007
#define M1 998244353

#define tr(container, it) \
for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)

#define fast                        \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

ll power(ll x, ll n)
{
    ll result = 1;
    while (n)
    {
        if (n % 2 == 1)
            result = result * x;
        n = n / 2;
        x = x * x;
    }
    return result;
}

ll gcd(ll a, ll b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

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

inline ll mul(ll x, ll y, ll m)
{
    ll z = 1LL * x * y;
    if (z >= m)
    {
        z %= m;
    }
    return z;
}

ll powmod(ll x, ll y, ll m)
{
    ll r = 1;
    while (y)
    {
        if (y & 1)
        {
            r = mul(r, x, m);
        }
        y >>= 1;
        x = mul(x, x, m);
    }
    return r;
}



void start()
{
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
/***********************************************************************************************************/

int main()
{
    start();
    string c, d;
    cin>>c>>d;
    int a=c.length(), b=d.length();
    if (a<b)
    {
        cout<<"LESS";
    }
    else if (a>b)
    {
        cout<<"GREATER";
    }
    else
    {
        for (int i=0;i<a;i++)
        {
            if (c[i]<d[i])
            {
                cout<<"LESS";
                return 0;
            }
            else if (c[i]>d[i])
            {
                cout<<"GREATER";
                return 0;
            }
        }
        cout<<"EQUAL";
    }

    return 0;
}

Measured memory_bytes: 3664
#!/usr/bin/env python
# -*- coding: utf-8 -*-

IN = 'sample-1.in'  # sample case for local test
def local_test():
    try:
        from pcm.utils import set_stdin
        import sys
        import os
        if len(sys.argv) == 1:
            set_stdin(os.path.dirname(__file__) + '/test/' + IN)
    except:
        pass


def preprocess():
    import sys
    import os
    import time
    import re
    from pydoc import help
    import string
    import math
    import numpy as np
    from operator import itemgetter
    from collections import Counter
    from collections import deque
    from collections import defaultdict as dd
    import fractions
    from heapq import heappop, heappush, heapify
    import array
    from bisect import bisect_left, bisect_right, insort_left, insort_right
    from copy import deepcopy as dcopy
    import itertools
    sys.setrecursionlimit(10**7)
    INF = 10**20
    GOSA = 1.0 / 10**10
    MOD = 10**9+7
    def LI(): return [int(x) for x in sys.stdin.readline().split()]
    def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
    def LF(): return [float(x) for x in sys.stdin.readline().split()]
    def LS(): return sys.stdin.readline().split()
    def I(): return int(sys.stdin.readline())
    def F(): return float(sys.stdin.readline())
    def DP(N, M, first): return [[first] * M for n in range(N)]
    def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]


def solve():
    global S, N
    N = int(input())

    S = []
    for n in range(N):
        S.append(list(input()))


    res = 0
    for n in range(N):
        if check(n):
            res += N

    print(res)

def check(move):
    for i in range(N):
        for j in range(i+1, N):
            if S[(i-move)%N][j] != S[(j-move)%N][i]:
                return False
    return True


if __name__ == "__main__":
    solve()




Measured memory_bytes: 42608
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt()+sc.nextInt()+sc.nextInt()+sc.nextInt();
        System.out.println(m/60);
        System.out.println(m%60);
    }
}

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

s_n = len(s)
t_n = len(t)

# 辞書順最小にするために末尾の部分文字列からチェック
for i in range(s_n - t_n, -1,-1):
    # 部分文字列
    match = s[i: i + t_n]
    
    isMatch=True
    for m_in,m_c in enumerate(match):
        if m_c == "?":
            continue
        
        if m_c != t[m_in]:
            isMatch = False
            break
    
    # 一致していなければ次を検索
    if not isMatch:
        continue

    # 一致している場合は、部分文字列を置き換える
    password=""
    if i > 0:
        password = s[:i]
    password += t
    if s_n > i + t_n:
        password+=s[i+t_n:]

    password = password.replace('?', 'a')  # 辞書順最小にするために、残りの?をaに置き換えておく
    print(password)
    exit()
    
print("UNRESTORABLE")

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

int yakusuu(int n) {
    int ret = 0;

    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) ret++;
    }

    return ret * 2;
}

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

    int ans = 0;
    for (int i = 1; i <= n; i += 2) {
        if (yakusuu(i) == 8) ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int32_t main()
{
	int n=in();
	vector<int> x(n),y(n);
	for(int i=0;i<n;i++)x[i]=in(),y[i]=in();
	vector<int> diff;
	vector<int> sum;
	for(int i=0;i<n;i++)diff.push_back(x[i]-y[i]),sum.push_back(x[i]+y[i]);
	sort(all(diff));sort(all(sum));
	
	int ans=max(abs(diff[0]-diff[n-1]),abs(sum[0]-sum[n-1]));
	cout<<ans;
	
	
}


Measured memory_bytes: 9772
main=do
 [x,y,tx,ty]<-map read.words<$>getLine
 let r = replicate (ty-y) 'U'++replicate (tx-x) 'R' 
 let l = map (\x -> if x == 'U' then 'D' else 'L') r
 putStrLn$r++l++"LU"++r++"RDRD"++l++"LU"

Measured memory_bytes: 1276
x = [[0]*3 for _ in range(3)]
a = [[0]*3 for _ in range(3)]

for i in range(3):
    a[i][0],a[i][1],a[i][2] = list(map(int,input().split()))
N = int(input())
for i in range(N):
    b = int(input())
    for j in range(3):
        for k in range(3):
            if b == a[j][k]:
                x[j][k] += 1

for i in range(3):
    if x[1][i]==x[2][i]==x[0][i]==1 \
    or x[i][1]==x[i][2]==x[i][0]==1 \
    or x[1][1]==x[2][2]==x[0][0]==1 \
    or x[0][2]==x[1][1]==x[2][0]==1:
        print('Yes')
        exit()

print('No')


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

struct G {
    int v, y, x;
    bool operator<(const G &g) const {
        return v > g.v;
    }
};

int ans = 10000, h, w;
char s[105][105];
int c[105][105];

int solve() {
    rep(i, 0, 105) rep(j, 0, 105) {
        c[i][j] = 10000;
    }
    if (s[0][0]=='#') c[0][0] = 1;
    else c[0][0] = 0;

    rep(y, 0, h) rep(x, 0, w) {
        if (y!=h-1) {
            int v;
            if (s[y][x]=='.' && s[y+1][x]=='#') v = c[y][x]+1;
            else v = c[y][x];
            c[y+1][x] = min(c[y+1][x], v);
        }
        if (x!=w-1) {
            int v;
            if (s[y][x]=='.' && s[y][x+1]=='#') v = c[y][x]+1;
            else v = c[y][x];
            c[y][x+1] = min(c[y][x+1], v);
        }

    }


}

int main(void) {
    cin >> h >> w;
    rep(i, 0, h) scanf("%s", s[i]);

    solve();

    cout << c[h-1][w-1] << endl;

	return 0;
}


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

#define N 100009

using namespace std;

const long long int mod=1e9+7;
long long int fac[N];

int main(){
	int i,j,t1,t2,t3,t4,n,m;
	long long int buf1,buf2,buf3,buf4,ans=0;
	fac[0]=fac[1]=1;
	for(i=2;i<=100000;i++){
		fac[i]=(fac[i-1]*i)%mod;
	}
	scanf("%d %d",&n,&m);
	// dog first
	if(m==n || m==n-1){
		buf1=(fac[m]*fac[n])%mod;
		ans+=buf1;
		ans%=mod;
	}
	// monkey first
	if(n==m || n==m-1){
		buf1=(fac[m]*fac[n])%mod;
		ans+=buf1;
		ans%=mod;
	}
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 1024
# ENV[Z = 'RUBY_THREAD_VM_STACK_SIZE'] || exec( { Z => '50000000' },'ruby',$0)
# readlines.map(&:chomp!).map { |e| e.split.map(&:to_i) }
# gets.split.map(&:to_i)
n,m,q = gets.split.map(&:to_i)

line = []
q.times do
  line << gets.chomp.split.map(&:to_i)
end



a = [*1..m].repeated_combination(n).to_a
max_s = 0
a.each do |arr|
  s = 0
  line.each do |l|
    if (arr[l[1]-1] - arr[l[0]-1]) == l[2] 
      s += l[3]
    end
  end
  if max_s < s
    max_s = s
  end
end

puts max_s


Measured memory_bytes: 27688
#include <bits/stdc++.h>
using namespace std;
int main(){
    string n;
    cin >> n;
    int digitSum = 0;
    for(int i=0; i<n.size(); i++){
        digitSum += n[i] - '0';
    }
    if(stoi(n)%digitSum==0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

int main()
{
    int K, A, B;
    cin >> K >> A >> B;

    for (int i = A; i <= B; i++)
    {
        if (i%K == 0)
        {
            cout << "OK";
            exit(0);
        }
        
    }

    cout << "NG";
    
}

Measured memory_bytes: 3636
/* ex 7_1
   Stuartyg */

#include <stdio.h>
#include <math.h>
int N = 245;
int D = 55;
typedef struct point{ //頂点を表す構造体pointの定義
    int x_elem;
    int y_elem;
}point;

point shift_point(point apex,int x_diff,int y_diff); //プロトタイプ宣言

int main(void){
    point apex,vertex,top,peak; //頂点の名前
    int x_diff,y_diff;
    scanf("%d %d %d %d",&apex.x_elem,&apex.y_elem,&vertex.x_elem,&vertex.y_elem);
    x_diff = vertex.x_elem-apex.x_elem; //(x2-x1)
    y_diff = vertex.y_elem-apex.y_elem; //(y2-y1)
    
    //座標を求める
    top = shift_point(vertex,x_diff,y_diff);
    peak = shift_point(apex,x_diff,y_diff);
    //出力
    printf("%d %d ",top.x_elem, top.y_elem);
    printf("%d %d\n",peak.x_elem, peak.y_elem);
    return 0;
}

//移動させた頂点を返す関数
point shift_point(point apex,int x_diff,int y_diff){
    point vertex;
    vertex.x_elem = apex.x_elem-y_diff;
    vertex.y_elem = apex.y_elem+x_diff;
    return vertex;
}

Measured memory_bytes: 1704
#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,x;
  cin >> n >> x;
  if(x == 1 || x == 2*n-1) cout << "No" << endl;
  else{
    cout << "Yes" << endl;
    vector<int> ans(2*n);
    for(int i = 0; i < ans.size(); i++){
      ans[i] = i;
    }
    if(x != n){
      if(x < n){
        ans[n-1] = x;
        ans[x] = n-1;
        ans[n] = 1;
        ans[1] = n;
      }else{
        ans[n+1] = x;
        ans[x] = n+1;
        ans[2*n-1] = n;
        ans[n] = 2*n-1;
      }
      
    }

    for(int i = 1; i <= 2*n-1; i++){
      cout << ans[i] << endl;
    }
  }

  return 0;
}

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

int main(void) {
  string s;
  cin >> s;
  
  if (s.at(2) == s.at(3) && s.at(4) == s.at(5))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  
  return 0;
}

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

inline long long f(long long x, long long y) {
    long long num = x/y;
    return (y + y * num) * num / 2;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long N;
    cin >> N;
    long long result = (N+1)*N/2 - f(N,3) - f(N,5) + f(N, 15);
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int count = 0;
  int count1 = 0;
  for(int i=0;i<3;i++){
    if(S[i]=='R'){
    	count1++;
      if(count1 > count){
          count = count1;
        }
    }else{
        if(count1 > count){
          count = count1;
        }
    	count1=0;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int in,j;
        Scanner scanner = new Scanner(System.in);
        in = scanner.nextInt();
        j = scanner.nextInt();
        int ass;
        int sum=0;
        for(int i=0;i<j;i++){
            ass =scanner.nextInt();
            sum+= ass;
        }
        if(sum>in){
            System.out.println("-1");
        } else {
            System.out.println(in-sum);
                    }

    }
}


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

int main(void){
	int W,H;
	while(cin){
		cin >> H >> W;
		if(W==0&&H==0) break;
		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++){
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))

    minCost = [float('inf')] * N
    minCost[0] = 0

    for i, h in enumerate(H):
        for k in range(1, K + 1):
            if i + k >= N:
                break
            minCost[i + k] = min(minCost[i + k], minCost[i] + abs(h - H[i + k]))

    print(minCost[N - 1])


sol()

Measured memory_bytes: 54876
#include <iostream>

using namespace std;

int main()
{
	int a, b, k, i;

	cin >> a >> b >> k;

	if(b-a < 2*k)
		for(i=0; a+i <= b; i++) cout << a+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;
	}

	return 0;
}

Measured memory_bytes: 256
#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>
#include <iterator>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int X;
	cin >> X;
	int tmp_j, divide_count;
	for (int j = X; j >= 2; j--) {
		for (int i = 2; i <= j; i++) {
			tmp_j = j;
			//iで割り続けて1になるか
			divide_count = 0;
			while (true) {
				if (tmp_j % i == 0) {
					tmp_j /= i;
					divide_count++;
				}
				else if (tmp_j == 1) {
					if (divide_count >= 2) {
						cout << j;
						return 0;
					}
					else {
						break;
					}
				}
				else {
					break;
				}

			}
		}
	}
	cout << 1;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] x = new int[5];
        for (int i=0;i<5;i++){
            x[i] = sc.nextInt();
        }
        for (int i=0;i<5;i++){
            if (x[i]==0)System.out.println(i+1);
        }
    }
}

Measured memory_bytes: 35708
#include <iostream>
#include <map>

void relax(long long &a, long long b, long long c) {
  if (b != -1 && (a == -1 || a > b + c)) {
    a = b + c;
  }
}

long long search(long long N, long long A, long long B, long long C, long long D, std::map <long long, long long> &m) {
  //std::cerr << "\t" << N << std::endl;
  if (N == 0) {
    return 0;
  }
  if (N == 1) {
    return D;
  }
  if (m.count(N) > 0) {
    //std::cerr << "\tm[N]=" << m[N] << std::endl;
    return m[N];
  }
  long long best = -1;

  if ((__int128)D * (N - N / 2) < A) {
    relax(best, search(N / 2, A, B, C, D, m), D * (N - N / 2));
  }
  if (N % 2 == 0) {
    //std::cerr << "\tN=" << N << "\tA=" << A << std::endl;
    relax(best, search(N / 2, A, B, C, D, m), A);
  } else if (N % 2 != 0 && N > 2) {
    relax(best, search(N / 2, A, B, C, D, m), A + D * (N % 2));
    relax(best, search((N + 1) / 2, A, B, C, D, m), A + D * (2 - N % 2));
  }

  if ((__int128)D * (N - N / 3) < B) {
    relax(best, search(N / 3, A, B, C, D, m), D * (N - N / 3));
  }
  if (N % 3 == 0) {
    relax(best, search(N / 3, A, B, C, D, m), B);
  } else if (N % 3 != 0 && N > 3) {
    relax(best, search(N / 3, A, B, C, D, m), B + D * (N % 3));
    //std::cerr << "\tN=" << N << "\tB+D(3-N%3)=" << (B + D * (3 - N % 3)) << std::endl;
    relax(best, search((N + 2) / 3, A, B, C, D, m), B + D * (3 - N % 3));
  }

  if ((__int128)D * (N - N / 5) < C) {
    relax(best, search(N / 5, A, B, C, D, m), D * (N - N / 5));
  }
  if (N % 5 == 0) {
    relax(best, search(N / 5, A, B, C, D, m), C);
  } else if (N % 5 != 0 && N > 5) {
    relax(best, search(N / 5, A, B, C, D, m), C + D * (N % 5));
    relax(best, search((N + 4) / 5, A, B, C, D, m), C + D * (5 - N % 5));
  }

  m[N] = best;
  return best;
}

void solve() {
  long long N, A, B, C, D;
  std::cin >> N >> A >> B >> C >> D;
  std::map <long long, long long> m;
  long long res = search(N, A, B, C, D, m);
  std::cout << res << std::endl;
}

int main() {
  int T;
  std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 4388
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	int cmptype=1; // 0-min 1-max
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
		return cmptype^((B.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-B.first));
	}
	void add(V a, V b) { // add ax+b
		Q.push_front({a,b});
		while(Q.size()>=3 && !dodo(Q[0],Q[1],Q[2]))
			Q[1]=Q[0], Q.pop_front();
	}
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			((cmptype^((calc(Q[M],x)>=calc(Q[M+1],x))))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};


int N;
ll T[303030],LS[303030],RS[303030];
int M;
ConvexHull<ll> LC, RC;
ll LD[303030],RD[303030],inc[303030],ninc[303030];
ll tmemo[303030];

void dfs(int LL,int RR) {
	if(RR-LL<=2) return;
	int MM=(LL+RR)/2;
	dfs(LL,MM);
	dfs(MM,RR);
	
	ConvexHull<ll> TLC, TRC;
	TLC.add(0,0);
	TRC.add(0,0);
	int i,j;
	for(i=LL;i<RR;i++) {
		if(i<MM) TLC.add(-(i+1), 1LL*i*(i+1)/2 + LD[i+1] + LS[i+1]);
		else tmemo[i]=TLC.query(i+1) + 1LL*(i+1)*(i+2)/2 - LS[i+1]+RD[N-1-i];
	}
	for(j=RR-1;j>=LL;j--) {
		i=N-1-j;
		if(j>=MM) TRC.add(-(i+1), 1LL*i*(i+1)/2 + RD[i+1] + RS[i+1]);
		else tmemo[j]=TRC.query(i+1) + 1LL*(i+1)*(i+2)/2 - RS[i+1]+LD[j];
	}
	
	ll ma=-1LL<<60;
	for(i=RR-1;i>=MM;i--){
		ma=max(ma,tmemo[i]);
		inc[i]=max(inc[i],ma);
	}
	ma=-1LL<<60;
	for(i=LL;i<MM;i++){
		ma=max(ma,tmemo[i]);
		inc[i]=max(inc[i],ma);
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	
	LC.add(0,0);
	RC.add(0,0);
	FOR(i,N) {
		LS[i+1]=LS[i]+T[i];
		LD[i+1]=max(LD[i], LC.query(i+1) + 1LL*(i+1)*(i+2)/2 - LS[i+1]);
		LC.add(-(i+1), 1LL*i*(i+1)/2 + LD[i+1] + LS[i+1]);
		
		RS[i+1]=RS[i]+T[N-1-i];
		RD[i+1]=max(RD[i], RC.query(i+1) + 1LL*(i+1)*(i+2)/2 - RS[i+1]);
		RC.add(-(i+1), 1LL*i*(i+1)/2 + RD[i+1] + RS[i+1]);
	}
	FOR(i,N) {
		ninc[i]=LD[i]+RD[N-1-i];
		inc[i]=1-T[i];
	}
	dfs(0,N);
	
	
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--;
		cout<<max(ninc[x], inc[x] + T[x] - y)<<endl;
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

int main() {
	int n;cin >>n;
	int cnt_ac = 0;
	int cnt_wa = 0;
	int cnt_tle = 0;
	int cnt_re = 0;
	for (int i=0;i<n;++i){
		string s;cin >> s;
		if(s=="AC") {
			++cnt_ac;
		} else if(s=="WA") {
			++cnt_wa;
		} else if(s=="TLE") {
			++cnt_tle;
		} else if(s=="RE") {
			++cnt_re;
		}
	}
	cout << "AC x "<< cnt_ac << endl;
	cout << "WA x "<< cnt_wa << endl;
	cout << "TLE x "<< cnt_tle << endl;
	cout << "RE x "<< cnt_re << endl;
	return 0;
}

Measured memory_bytes: 3588
//   __      __       .__           .____________                   __________        __ ________   __                 
//  /  \    /  \ ____ |_________  __| _\______   \__ __  ____  _____\______   \__ ___/  |\_____  \ |  | ______  ___.__.
//  \   \/\/   _/ __ \|  \_  __ \/ __ | |    |  _|  |  \/ ___\/  ___/|    |  _|  |  \   __/   |   \|  |/ \__  \<   |  |
//   \        /\  ___/|  ||  | \/ /_/ | |    |   |  |  / /_/  \___ \ |    |   |  |  /|  |/    |    |    < / __ \\___  |
//    \__/\  /  \___  |__||__|  \____ | |______  |____/\___  /____  >|______  |____/ |__|\_______  |__|_ (____  / ____|
//         \/       \/               \/        \/     /_____/     \/        \/                   \/     \/    \/\/     

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

using namespace std;

void solve()
{
    ll n;
    cin >> n;
    ll a[n];
    map <ll, ll> l, r;
    for(ll i = 0; i < n; i++)
    {
        cin >> a[i];
        l[a[i] + i]++;
        r[i - a[i]]++;
    }
    ll ans = 0;
    for(auto i : l)
        ans += i.ss * r[i.ff];
    cout << ans << endl;
}

int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q = 1;
	//cin >> q;
	for(int i = 1; i <= q; i++)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 39496
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S;
		S = sc.next();

		int cnt = 0;
		int cntN = 0;
		for (int i = 0; i < S.length(); i++) {
			if (S.charAt(i) == 'o') {
				cnt++;
			} else {
				cntN++;
			}
		}

		if (S.length() == 15 && cnt < 8) {
			System.out.println("NO");
		} else if (S.length() == 15 && cnt >= 8) {
			System.out.println("YES");
		} else if (S.length() < 15 && cntN <= 7) {
			System.out.println("YES");
		} else if (S.length() < 15 && cntN >= 8) {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 23636
/* Coached by Dukkha */
#include <stdio.h>

#define N 100000

int oo[1 + (N - 1) * 2], oj[1 + (N - 1) * 2];

int link(int o, int j) {
	static int _ = 1;

	oo[_] = o, oj[_] = j;
	return _++;
}

int ae[N], pp[N], dd[N], sz[N];

void dfs(int p, int i, int d) {
	int o;

	pp[i] = p;
	dd[i] = d;
	sz[i] = 1;
	for (o = ae[i]; o; o = oo[o]) {
		int j = oj[o];

		if (j != p) {
			dfs(i, j, d + 1);
			sz[i] += sz[j];
		}
	}
}

int main() {
	int n, h, i, j, d;

	scanf("%d", &n);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ae[i] = link(ae[i], j);
		ae[j] = link(ae[j], i);
	}
	dfs(-1, 0, 0);
	d = dd[n - 1] / 2 + 1;
	i = n - 1;
	while (dd[i] != d)
		i = pp[i];
	printf(sz[i] >= n - sz[i] ? "Snuke\n" : "Fennec\n");
	return 0;
}


Measured memory_bytes: 9472