akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var B = cin.ReadLine;
            int result = 0;
            int counter = 0;

            List<char> ch = new List<char>() {'A','C','G','T' };
            foreach (var item in B)
            {
                if (ch.Contains(item))
                {
                    ++counter;
                }
                else
                {
                    counter = 0;
                }
                if (counter >= result)
                {
                    result = counter;
                }
            }

            Console.Write(result);
        }

    }
    public class deci
    {
        public bool IsFinish { get; set; } = false;
        public int Len { get; set; }
    }
    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;
typedef vector<string> vs;
const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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

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

ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	ll n,ans=INF;
	cin >> n;
	vll a(n);
	rep(i,n) cin >> a[i];
	for(ll i=1;i<=100;i++){
		ll tmp=0;
		rep(j,n){
			tmp+=pow(a[j]-i,2);
		}
		chmin(ans,tmp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int num1,num2;
  char ope,str[32];
  fgets(str,sizeof(str),stdin);
  sscanf(str,"%d %c %d",&num1,&ope,&num2);
  switch (ope)
  {
    case '+':
      printf("%d\n",num1+num2);
      break;
    case '-':
      printf("%d\n",num1-num2);
      break;
    default:
      printf("error\n");
      break;
  }
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

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

    const int M = 256;

    int N;
    while (cin >> N, N) {
        V I(N);
        rep(i, N) cin >> I[i];

        double mi = 1e9;
        int S, A, C;
        rep(s, 15 + 1) {
            rep(a, 15 + 1) {
                rep(c, 15 + 1) {
                    int r = s;
                    map<int, int> mp;   // O(i), #occurence
                    rep(i, N) {
                        r = (a * r + c) % M;
                        mp[(I[i] + r) % M]++;
                    }

                    double h = 0.;
                    for (auto p : mp) {
                        h += - ((p.second * 1.) / N) * log((p.second * 1.) / N);
                    }

                    if (h + 1e-10 < mi) {
                        mi = h;
                        S = s, A = a, C = c;
                    }
                }
            }
        }

        cout << S << " " << A << " " << C << endl;
    }

}

Measured memory_bytes: 3388
#include <iostream>
#include <string>
#include <stack>

using std::cin;
using std::cout;
using std::endl;

int main(void) {
	int q,p,n;
	char c;
	std::stack<bool> lang;
	cin >> q;
	long r = 0;
	long l = 0;
	for (int t = 0; t < q; t++) {
		cin >> p;
		cin >> c;
		cin >> n;
		if ( c == '(' ) {
			r += n;
		}
		else {
			l += n;
		}

		if ( r == l ) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3068
/*
author:brownsands
       IIITA
       19-04-2019*/
    
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back 

int a,b,c,t;
signed main(){
              ios_base::sync_with_stdio(false);
              cin.tie(NULL);
              cout.tie(NULL);
        cin>>a>>b>>t;
        c=t/a;
        cout<<c*b;
           
                     return 0;
}
       


Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp15
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] ST = Console.ReadLine().Split();
            int[] AB = Console.ReadLine().Split().Select(int.Parse).ToArray();
            string U = Console.ReadLine();
            if(U == ST[0])
            {
                AB[0]--;
            }
            else
            {
                AB[1]--;
            }
            Console.WriteLine(string.Join(" ", AB));
        }
    }
}


Measured memory_bytes: 13396
N = int(input())
c = [list(map(int, input().split())) for _ in range(N - 1)]
anslst = [0] * N
for i in range(N - 1):
    ans = c[i][1] + c[i][0]
    for j in range(i + 1, N - 1):
        if ans <= c[j][1]:
            ans += (c[j][1] - ans) + c[j][0]
        else:
            sho, amari = divmod(ans, c[j][2])
            if amari == 0:
                ans += c[j][0]
            else:
                ans += c[j][0] + (((sho + 1) * c[j][2]) - ans)

    anslst[i] = ans

for i in anslst:
    print(i)

Measured memory_bytes: 3188
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

typedef unsigned long long ULLONG;
typedef long long LLONG;

template <class _T> static _T tp_abs(const _T& a) {
	return ((a < 0) ? (a * -1) : a);
}
template <class _T> static _T tp_min(_T a, _T b) {
	return a < b ? a : b;
}
template <class _T> static _T tp_max(_T a, _T b) {
	return a > b ? a : b;
}
template<class _T> static void getint(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}
static void getstring(char* buff) {
	if (scanf(" %s", buff) < 0) {
		printf("getstr error!\n");
	}
}
static const long long MOD_NUM = 1000000007LL;
template <class _T> static _T tp_pow(int base, int exp)
{
	_T ans = 1;

	for (int i = 0; i < exp; i++) {
		ans *= base;
	}
	return ans;
}

static void C_task();

int main()
{
	C_task();
	fflush(stdout);
	return 0;
}

static void C_task()
{
	LLONG A;
	std::cin >> A;
	long double B;
	std::cin >> B;

	long double ans = A * B;
	printf("%lld\n", (LLONG)ans);
}


Measured memory_bytes: 3796
## ABC 049C
## C - Daydream
import sys

s = input()
letter = ['dream','dreamer','erase','eraser']

ll = len(s)
while ll > 0:
    for le in range(len(letter)):
        if(ll-len(letter[le]) < 0):
            continue
        ss = s[ll-len(letter[le]):ll]
        # print("out:"+ss,letter[le])
        if(letter[le] == ss):
            ll -= len(letter[le])
            break
        else:
            if(le == len(letter)-1):
                print('NO')
                sys.exit()
            else:
                continue
        
print('YES')


Measured memory_bytes: 3188
b[101][101];xg,yg;r(x,y,c){if(c!=b[x][y])return 0;if(x==xg&&y==yg)return 1;b[x][y]=0;return r(x+1,y,c)||r(x,y+1,c)||r(x-1,y,c)||r(x,y-1,c)?1:0;}main(xs,ys,n,c,d,x,y){for(;scanf("%d%d",&x,&y),x;puts(b[xs][ys]&&b[xg][yg]&&b[xs][ys]==b[xg][yg]&&r(xs,ys,b[xs][ys])?"OK":"NG"))for(scanf("%d%d%d%d%d",&xs,&ys,&xg,&yg,&n);n;n--)if(scanf("%d%d%d%d",&c,&d,&x,&y),d)b[x][y]=b[x+1][y]=b[x][y+1]=b[x+1][y+1]=b[x][y+2]=b[x+1][y+2]=b[x][y+3]=b[x+1][y+3]=c;else b[x][y]=b[x+1][y]=b[x+2][y]=b[x+3][y]=b[x][y+1]=b[x+1][y+1]=b[x+2][y+1]=b[x+3][y+1]=c;return 0;}

Measured memory_bytes: 0
// A - Dodecagon

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const int MOD = 1e9 + 7;

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

	int ans = 3 * r * r;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))

sum_post = sum(A) / (4 * M)
count = 0

for i in range(N):
    if A[i] >= sum_post:
        count += 1

if count >= M:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define re register
#define M 1000000007
inline int read(){
	re int t=0;
	re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0'){
		t=(t<<3)+(t<<1)+v-48;
		v=getchar();
	}
	return t;
}
using namespace std;
int n,head[2000002],cnt,ans[2000002],fa[2000002],f[2000002],jc[2000002],num[2000002],inv[2000002],siz[2000002],siz1[2000002];
struct edge{
	int to,next;
}e[2000002];
inline int C(re int x,re int y){
	return 1ll*jc[x]*inv[y]%M*inv[x-y]%M;
}
inline void add(re int x,re int y){
	e[++cnt].to=y;
	e[cnt].next=head[x];
	head[x]=cnt;
}
inline void dp(re int x,re int y){
	ans[x]=1;fa[x]=y;siz[x]=1;
	for(re int i=head[x];i;i=e[i].next)
	if(e[i].to^y){
	dp(e[i].to,x);
	ans[x]=1ll*ans[x]*ans[e[i].to]%M*C(siz[x]-1+siz[e[i].to],siz[e[i].to])%M;siz[x]+=siz[e[i].to];}
}
inline int ksm(re int x,re int y){
	re int ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%M;
		x=1ll*x*x%M;
		y>>=1;
	}
	return ans;
}
inline void dp1(re int x,re int y){
	if(x!=1)ans[x]=1ll*ans[x]*y%M*C(siz[x]-1+n-siz[x],n-siz[x])%M;
	for(re int i=head[x];i;i=e[i].next)if(e[i].to^fa[x])dp1(e[i].to,1ll*ans[x]*ksm(ans[e[i].to],M-2)%M*ksm(C(n-1,siz[e[i].to]),M-2)%M);
}
signed main(){
	n=read();
	jc[0]=1;n*=2;
	for(re int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%M;
	inv[n]=ksm(jc[n],M-2);inv[0]=1;
	for(re int i=n-1;i;--i)inv[i]=1ll*(i+1)*inv[i+1]%M;n/=2;
	for(re int i=1,x,y;i<n;++i){
		x=read();y=read();
		add(x,y);
		add(y,x);
	}
	dp(1,1);
	dp1(1,1);
	for(re int i=1;i<=n;++i)printf("%d\n",ans[i]);
}

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

bool red[100001] = {};
int ball[100001] = {};

int main(){
    int n, m, x, y;
    cin >> n >> m;
    red[1] = true;

    for(int i = 0; i < m; i++){
        cin >> x >> y;
        ball[x]--;
        ball[y]++;
        if(red[x])  red[y] = true;
        if(ball[x] == -1)   red[x] = false;
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) if(red[i])  ans++;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

#define fi first
#define se second

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

typedef pair<int,string> pis;

int n, a, s, g;
vector<vector<pis> > G;
vector<vector<pis> > rG;
bool reachable[50];

pair<string, set<int> > q[40*6 + 10];

void dfs(int nd, vector<vector<pis> > & Gra) {
	if(reachable[nd])
		return ;
	reachable[nd] = true;
	rep(i,Gra[nd].size()) {
		dfs(Gra[nd][i].fi, Gra);
	}
}

int main() {
	while(1) {
		cin >> n >> a >> s >> g;
		G.clear();
		rG.clear();
		rep(i,50) reachable[i] = false;
		rep(i, 40*6+10) q[i] = pair<string, set<int> >("", set<int>());
		if(!(n || a || s || g))
			break;
		G.resize(n);
		rG.resize(n);
		rep(i,a) {
			int x, y;
			string lab;
			cin >> x >> y >> lab;
			G[x].push_back(pis(y,lab));
			rG[y].push_back(pis(x,string(lab.rbegin(), lab.rend())));
		}
		dfs(g, rG);

		int len = 0;
		q[0].fi = "";
		q[0].se.insert(s);
		string res, tmp;
		res = tmp = "";
		while(len < 40*6+10) {
			for(set<int>::iterator it = q[len].se.begin();
					it != q[len].se.end(); it++) {
				if(*it == g) {
					if(res == "")
						res = q[len].fi;
					res = min(res, q[len].fi);
				}
				// 遷移
				rep(i, G[*it].size()) {
					string nex;
					nex = q[len].fi + G[*it][i].se;
					if(!reachable[G[*it][i].fi])
						continue;
					if(nex.size() < 40*6 + 10) {
						if(q[nex.size()].fi == "" || nex < q[nex.size()].fi) {
							q[nex.size()].fi = nex;
							q[nex.size()].se.clear();
						}
						if(q[nex.size()].fi == nex) {
							q[nex.size()].se.insert(G[*it][i].fi);
						}
					}
					else {
						if(tmp == "")
							tmp = nex;
						tmp = min(tmp, nex);
					}
				}
			}
			len++;
		}
		if(res == "" || (tmp != "" && tmp < res))
			cout << "NO" << endl;
		else
			cout << res << endl;
	}
}

Measured memory_bytes: 1704
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long int
void solve()
{
   ll n,k;
   cin>>n>>k;
   
   ll arr[n],ans=0,num;
   
   for(ll i=0;i<n;i++)
   {
   cin>>num;
   if(num>=k)
   ans++;
   }
   
   cout<<ans;
   return;
}

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

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>

using namespace std;
int main(){
int X;
int A,B,C;
cin >>A >>B >>C;
cin >>X;
int ans=0;
    for(int i=0;i<=A;i++){
        for(int l=0;l<=B;l++){
            for(int k=0;k<=C;k++){

            if(X==500*i+100*l+50*k){
            ans++;
            }
        }
    }
}
        cout << ans <<endl;


 return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;
class Main{
  public static void main(String args[]){
    Scanner scan=new Scanner(System.in);
    int n=scan.nextInt();
    int a,b;
    a=scan.nextInt();
    for(int i=1;i<n;i++){
      b=scan.nextInt();
      a=gcd(a,b);
    }
    System.out.println(a);
  }
  public static int gcd(int a,int b){
    if(b==0){
      return a;
    }else{
      return gcd(b,a%b);
    }
  }
}


Measured memory_bytes: 50184
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        for(int i=0; i<x; i++) {
            int[] a = new int[3];
            a[0] = scanner.nextInt();
            a[1] = scanner.nextInt();
            a[2] = scanner.nextInt();
            Arrays.sort(a);
            if(a[0]*a[0] + a[1]*a[1] == a[2]*a[2]) {
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }
}

Measured memory_bytes: 23344
import sys
alf = []
countchan = []
for i in range(26):
    alf.append(chr(ord("a")+i))
    countchan.append(0)
for i in sys.stdin.readlines():
    for i2 in range(26):
        countchan[i2] += i.count(chr(ord("a")+i2))
        countchan[i2] += i.count(chr(ord("A")+i2))
for i in range(26):
    print(alf[i]+" : "+str(countchan[i]))

Measured memory_bytes: 7408
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		long mod = (long)(1e9+7);
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		long K = input.nextLong();
		int[] A = new int[N+1];
		boolean[] vis = new boolean[N+1];
		boolean quick = false;
		vis[1]=true;
		int curIndex = 1;
		ArrayList<Integer> seq = new ArrayList<Integer>();
		seq.add(1);
		for (int i = 1; i <= N; i++) {
			A[i] = input.nextInt();
		}
		while (true) {
			K--;
			int temp = A[curIndex];
			curIndex=temp;
			if (vis[curIndex]) {
				while (seq.get(0)!=curIndex) {
					seq.remove(0);
				}
				break;
			} 
			else {
				seq.add(curIndex);
				vis[curIndex]=true;
			}
			if (K==0) {
				System.out.println(curIndex);
				quick = true;
				break;
			}
		}
		if (!quick) {
			long period = seq.size();
			int index = (int) (K%period);
			System.out.println(seq.get(index));
		}
	}
}

Measured memory_bytes: 51756
N = int(input())

if N < 10:
    print(N)
    exit()

n = N - int((len(str(N)) - 1) * '9')
tmp = (len(str(N)) - 1) * '9'
if len(str(n)) > (len(str(N)) - 1):
    tmp = str(n)[0] + tmp

res = 0
for t in tmp:
    res += int(t)

print(res)


Measured memory_bytes: 9136
#include <bits/stdc++.h>
#define ll long long
#define maxn 100010*5
using namespace std;

bool flag;

int n,m,cnt,head[maxn],col[maxn];

ll sum[5],ans;

struct E{
	int to,nxt,w;
}edge[maxn<<1];

void read(int &x){
	char s=getchar();x=0;
	while(s<'0'||s>'9') s=getchar();
	while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-48,s=getchar();
}

inline void add(int u,int v,int w){edge[++cnt]=(E){v,head[u],w};head[u]=cnt;}

void dfs(int u){
	sum[col[u]]++;
	for(int i=head[u];i;i=edge[i].nxt){
		if(edge[i].w==1) sum[3]++;
		if(col[edge[i].to]==-1){
			col[edge[i].to]=(col[u]+edge[i].w)%3;
			dfs(edge[i].to);
		}
		else if(col[edge[i].to]!=(col[u]+edge[i].w)%3) flag=true;
	}
}

int main(){
	read(n);read(m);
	for(int i=1,x,y;i<=m;i++){
		read(x);read(y);
		add(x,y,1);
		add(y,x,2);
	}
	memset(col,-1,sizeof(col));
	for(int i=1;i<=n;i++){
		if(col[i]==-1){
			memset(sum,0,sizeof(sum));
			flag=col[i]=0;
			dfs(i);
			if(flag){
				ans+=(sum[0]+sum[1]+sum[2])*(sum[0]+sum[1]+sum[2]);
				continue;
			}
			if(sum[0]==0||sum[1]==0||sum[2]==0){
				ans+=sum[3];
				continue;
			}
			ans+=sum[0]*sum[1]+sum[1]*sum[2]+sum[2]*sum[0];
		}
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 11520
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

typedef struct{
	TLong b;
	TLong c;
} BC;

int ASC(const int *a,const int *b){
	return (*a - *b);
}

int DESC(const int *p,const int *q){
	return ((BC *)q)->c - ((BC *)p)->c;
}

int main(int argc, char const *argv[])
{
	TLong n,m;
	TLong a[100003];
	BC bc[100003];
	TLong max = 0,sum = 0;
	TLong cnt = 0,pcnt = 0;

	scanf("%lld%lld",&n,&m);
	for (TLong i = 0; i < n; ++i)	scanf("%lld",&a[i]);
	for (TLong i = 0; i < m; ++i)	scanf("%lld%lld",&bc[i].b, &bc[i].c);
	qsort(a,n,sizeof(TLong),ASC);
	qsort(bc,m,sizeof(BC),DESC);

	for (TLong i = 0; i < n; ++i)
	{
		if(pcnt >= bc[cnt].b){
			++cnt;
			pcnt = 0;
			if(cnt >= m)	break;
		}
		if(a[i] < bc[cnt].c) a[i] = bc[cnt].c;
		else break;
		++pcnt;
	}
	// printf("*a = [");
	for (TLong i = 0; i < n; ++i){
	  sum += a[i];
	  // printf(" %lld ",a[i]);
	}
	// puts("]");
	printf("%lld\n", sum);
	return 0;
}


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

#define MAX_N 105
#define MAX_W 100005

long long i, T, G, ans, N, MW, V[MAX_N], W[MAX_N], memo[MAX_N][MAX_W];

long long value(long long id, long long w) {
  if (id == N || w == 0) return 0;
  if (memo[id][w] != -1) return memo[id][w];
  if (W[id] > w)         return memo[id][w] = value(id + 1, w);
  return memo[id][w] = max(value(id + 1, w), V[id] + value(id + 1, w - W[id]));
}

int main() {
   
    memset(memo, -1, sizeof memo);

    cin>>N>>MW;
   // scanf("%lld",&MW);
    for (i = 0; i < N; i++)
      cin>>W[i]>>V[i];
    ans = 0;
      ans = value(0, MW);

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

  return 0;
}

Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> arr, p, q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin >> n;
    p = vector<ll>(n);
    q = vector<ll>(n);
    arr = vector<ll>(n);
    for (ll i = 0; i < n; i++) {
        cin >> p[i];
        arr[i] = i + 1;
    }
    for (ll i = 0; i < n; i++) {
        cin >> q[i];
    }
    ll a = 0, b = 0, cnt = 0;
    do {
        ++cnt;
        if (arr == p) {
            a = cnt;
        }
        if (arr == q) {
            b = cnt;
        }
    } while (next_permutation(arr.begin(), arr.end()));
    cout << abs(a - b);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<vector<vector<int>>> rooms(4, vector<vector<int>>(3, vector<int>(10, 0)));
  int n; cin >> n;
  for (int i = 0; i < n; i++){
    int b, f, r, v; cin >> b >> f >> r >> v;
    rooms[b - 1][f - 1][r - 1] += v;
  }
  for (int i = 0; i < 4; i++){
    for (int j = 0; j < 3; j++){
      for (int k = 0; k < 10; k++){
        cout << " " << rooms[i][j][k];
      }
      cout << endl;
    }
    if (i != 3) cout << "####################" << endl;
  }
  return 0;
}


Measured memory_bytes: 3172
s = input()
_s = [a for a in s]
ss = set(_s)

_az = [chr(i) for i in range(ord('a'), ord('z')+1)]
az = set(_az)

diff = list(az - ss)
diff.sort()

if len(diff):
    print(diff[0])
else:
    print('None')

Measured memory_bytes: 4016
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)

void solve(long long N, std::vector<long long> x, std::vector<long long> y, std::vector<long long> h){
    rep(cx, 101){
        rep(cy, 101){
            ll H;
            bool ub=false;
            bool isGood = true;
            if(h[0]== 0)
                ub = true;
            H = abs(x[0]-cx)+abs(y[0]-cy) + h[0];
            for(ll i=1; i< N; i++){
                ll Hnew;
                Hnew = abs(x[i]-cx)+abs(y[i]-cy) + h[i];
                if(h[i] == 0){ //* new info is not accurate
                    if(ub){//* old info is not accurate
                        H = min(H, Hnew);
                    }
                    else{//* old info is exact, so only check conflict
                        if(Hnew< H){
                            isGood = false;
                            break;
                        }
                            
                    }
                }
                else{
                    if(ub){//* old info is not accurate
                        if(Hnew <= H){
                            ub = false; //* now info is exact
                            H = Hnew;
                        }
                        else{ //* Hnew > upperbound
                            isGood = false;
                            break;
                        }
                    }
                    else{ //* old info is exact
                        if(Hnew != H){
                            isGood = false;
                            break;
                        }
                            
                    }
                }
            }
            if(isGood){
                cout << cx << " " << cy << " " << H <<endl;
                return;
            }
            
        }
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> x(N);
    std::vector<long long> y(N);
    std::vector<long long> h(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
        scanf("%lld",&h[i]);
    }
    solve(N, std::move(x), std::move(y), std::move(h));
    return 0;
}


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


    using namespace std;
    typedef long long ll;
    # define M_PI  3.14159265358979323846
    const int MOD=1e9+7;

    void solve(){
        int n,k;
        cin>>n>>k;
        vector<int>a(n+1);
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int dp[n+1][k+1];
        dp[0][0]=1;
        for(int i=1;i<=k;i++)
            dp[0][i]=0;
        for(int i=1;i<=n;i++){
            vector<int>sum(k+1);
            sum[0]=dp[i-1][0];
            for(int j=1;j<=k;j++)
                sum[j]=(sum[j-1]+dp[i-1][j])%MOD;
            for(int j=0;j<=k;j++){
                if(j<=a[i])
                    dp[i][j]=sum[j];
                else{
                    int non_existing=j-a[i]-1;
                    dp[i][j]=(sum[j]-sum[non_existing]+MOD)%MOD;
                }
            }
            sum.clear();
        }
//        for(int i=0;i<=n;i++){
//            for(int j=0;j<=k;j++)
//                cout<<dp[i][j]<<" ";
//            cout<<"\n";
//        }
        cout<<dp[n][k];
    }

    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout<<fixed;
        cout<<setprecision(10);
        int t=1;
//        cin>>t;
        for(int i=1;i<=t;i++){
            solve();
        }
        return 0;
    }


Measured memory_bytes: 43436
s_list = list(input())
k = int(input())
s_sort = sorted(s_list)
a_list = []
for s in s_sort:
    idx = s_list.index(s)
    for i in range(1, 6):
        a_list.append("".join(s_list[idx:idx+i]))
    s_list[idx] = "@"
a = list(set(a_list))
for i, s in enumerate(a):
    if "@" in s:
        a[i] = s.replace("@", s_sort[0])
a = sorted(a)
print(a[k - 1])

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

int main() {
  //入力
  int a,b,c,d,e,k;
  cin>>a;
  cin >>b;
  cin >> c;
  cin >> d;
  cin >> e;
  cin >> k;
  //処理
  string ans;
  if(e-a>k)
  {
    ans=":(";
  }
  else
  {
    ans="Yay!";
  }

  //出力
  cout << ans << endl;
}


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

#define pb push_back
#define mp make_pair

const int MOD = 1e9+7;
const int MAX_N=1e5+10;

int N, M;
vector<int> g[MAX_N];
ll H[MAX_N];

void add_edge(int from, int to)
{
	g[from].push_back(to);
	g[to].push_back(from);
}

void solve()
{
	int ans = 0;
	for(int i=1;i<=N;++i){
		bool ok=true;
		for(int x : g[i]){
			if(H[x]>=H[i]){
				ok=false;
				break;
			}
		}
		if(ok)ans++;
	}
	cout << ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N >> M;
	for(int i=1;i<=N;++i) cin >> H[i];
	int a, b;
	for(int i=0;i<M;++i){
		cin >> a >> b;
		add_edge(a,b);
	}
	solve();
	return 0;
}


Measured memory_bytes: 9568
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s;
    std::cin >> s;
    if(s[0]==s[1] || s[1]==s[2] || s[2]==s[3]){
        std::cout << "Bad" << std::endl;
    }else{
        std::cout << "Good" << std::endl;
    }
}


Measured memory_bytes: 256
#include <cstdio>

int main() {
  int N;
  scanf("%d", &N);

  for (int i = 0; i < 100; ++i)
    for (int j = 0; j < 100; ++j)
      if (4*i + 7*j == N)
        return puts("Yes"), 0;

  puts("No");
}

Measured memory_bytes: 256
S = input()

head = int(S[:2])
tail = int(S[2:])

def mm(n):
    if n > 0 and n <= 12:
        return True

result = ""
if mm(head) and mm(tail):
    result = 'AMBIGUOUS'
elif mm(head) and not(mm(tail)):
    result = 'MMYY'
elif not(mm(head)) and mm(tail):
    result = 'YYMM'
else:
    result = 'NA'
print(result)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
    
        using namespace std;
        #define ll long long
        #define ld long double
        #define vll vector<ll>
        #define mll map<ll,ll>
        #define pll pair<ll,ll>
        #define ff first
        #define ss second
        #define pb push_back
        #define deb(x) cout<<#x<<" : "<<x<<endl;
        #define deb2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
        #define deb3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
        #define deb4(w,x,y,z) cout<<#w<<" : "<<w<<"\t"<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
        #define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #define printv(a)  for(ll i=0;i<a.size();i++)  cout<<a[i]<<" ";
       
       
        const int mod=998244353;
        const int N=1e6+5; 
        const ll inf=1e18+5;
       
        bool sortbysec(const pair<pair<ll,ll>,ll> &a, 
                          const pair<pair<ll,ll>,ll> &b) 
            { 
                return (a.second > b.second); 
            } 
            ll powermod(ll x, ll y, ll p)
            {
                ll res = 1;
                x = x % p;
                while (y > 0)
                {
                    if (y & 1) res = (res*x) % p;
                    y = y>>1;
                    x = (x*x) % p;
                }
                return res;
            }
           
            bool isprime(int n) 
            { 
                if (n <= 1)  return false; 
                if (n <= 3)  return true; 
                if (n%2 == 0 || n%3 == 0) return false; 
                for (int i=5; i*i<=n; i=i+6) 
                    if (n%i == 0 || n%(i+2) == 0) 
                       return false; 
               return true; 
            }
           
            
        int main()
        {
            FAST;
            string s;
            cin>>s;
            if(s[2]==s[3] && s[4]==s[5])
            cout<<"Yes";
            else
            cout<<"No";
               
            return 0;
        }

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
 
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        cs: chars,
    }

    let mut kioku = 0;
    let ans = dfs(&cs, 0, &mut kioku);

    if let Some(ans) = ans {
        for i in 0..3 {
            print!("{}", cs[i]);
            if ans & 2usize.pow(i as u32) != 0  {
                print!("+");
            } else {
                print!("-");
            }
        }
        print!("{}", cs[3]);
        println!("=7");
    }       
}

fn dfs(cs: &Vec<char>, pos: usize, kioku: &mut usize) -> Option<usize>{
    if pos == 3 {
        let mut ans: i32= cs[0].to_digit(10).unwrap() as i32;
        for i in 1..4 {
            if *kioku & 2usize.pow(i-1) != 0 {
                ans = ans + cs[i as usize].to_digit(10).unwrap() as i32;
            } else {
                ans = ans - cs[i as usize].to_digit(10).unwrap() as i32;
            }
        }
        if ans == 7 {
            //println!("kioku: {}", *kioku);
            return Some(*kioku);
        } else {
            return None;
        }

    }

    let ret1 = dfs(cs, pos+1, kioku);
    *kioku = *kioku + 2usize.pow(pos as u32);
    let ret2 = dfs(cs, pos+1, kioku);
    *kioku = *kioku - 2usize.pow(pos as u32);

    if ret1.is_some() {
        return ret1; 
    } else if ret2.is_some() {
        return ret2;
    } else {
        return None;
    }
}

Measured memory_bytes: 4352
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int coin[]={10,50,100,500};
int main(){
	int a[4],b[4],k,c,s=1;
	while(cin>>c,c){
		if(s!=1)cout<<endl;
		s=-c;
		rep(i,4)cin>>b[i],s+=b[i]*coin[i],a[i]=0;
		rep(i,4)while(s>=coin[3-i])s-=coin[3-i],a[3-i]++;
		rep(i,4){
			k=b[i]-a[i];if(k>0)cout<<coin[i]<<" "<<k<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
n = int(input())
a = list(map(int, input().split()))

trade = 0
for i in range(n):
    minj = i 
    for j in range(i, n):
        if a[j] < a[minj]:
            minj = j
    if i != minj:
        trade += 1
    a[i], a[minj] = a[minj], a[i]
    
print(' '.join(map(str, a)))
print(trade)


Measured memory_bytes: 5596
n, x = map(int, raw_input().split())
if 2 > x or n*2-2 < x:
    print "No"
    exit()
else:
    r = range(1, 2*n)
    i = x - n
    r = r[i:] + r[:i]
    # print r
    print "Yes"
    for ri in r:
        print ri

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

using namespace std;
#define ll long long

int main (void) {
    ll n;
    int k;

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

    ll ans = 1;
    for(ll i = 1; i < n; ++i){
        if((pow(k, i) - 1) >= n){
            ans = i;
            break;
        }
    }
    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
#define fir first
#define sec second
typedef long long ll;
////////////////////////////////////////////////////////////

int main(){
	int n;
	cin >> n;
	double ans = 0;
	rep(i,0,n){
		double m;
		string s;
		cin >> m >> s;
		if( s == "JPY" ) ans += m;
		else ans += m * 380000;
	}
	cout << ans << endl;
	ret 0;
}

Measured memory_bytes: 256
x,k,d=map(int,input().split())
c=abs(x)//d
n1=abs(x)-c*d
n2=n1-d
if k<=c:
  print(abs(abs(x)-k*d))
  exit()
if k%2==c%2:
  print(abs(n1))
else:
  print(abs(n2))

Measured memory_bytes: 9180
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;



int main(){

	int s, a[10000], ans=100000;
	cin >> s;
	a[0]=s;
	int n=0;
	while(n<10000){
		if(a[n]%2!=0){
			n++;
			a[n]=3*a[n-1]+1;
		} else {
			n++;
			a[n]=a[n-1]/2;
		}
	}
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(a[i]==a[j]){
				if(ans>j+1){
					ans=j+1;
				}
			}
		}
	}
	cout << ans << endl;

	return 0;
}


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

#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 trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define hash dhsjakhd
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 eng(seed);

uniform_int_distribution<> DD(0, (1ll << 31));

ll random2(){
    return (ll(DD(eng))*(1ll << 31) + ll(DD(eng))) & ((1ll << 62ll)-1);
}

ll n,m,T,k,q;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const ll MAXN = 501;

ll M[MAXN][MAXN] = {0};
ll A[MAXN][MAXN] = {0};
ll B[MAXN][MAXN] = {0};


int DP1[MAXN][MAXN][2] = {0};
bool DP1C[MAXN][MAXN][2] = {0};

int dp1(int i, int j, int kind){
    if(i > j)return 0;
    if(kind == -1)return j-i+1;
    if(DP1C[i][j][kind])return DP1[i][j][kind];
    int ans = dp1(i,j-1,kind) + dp1(j,n-1,kind-1);
    DP1[i][j][kind] = ans;
    DP1C[i][j][kind] = 1;
    return ans;
}

int enumerate(int a, int b, int c){
    if(b == n){
        return 20958500 + a;
    }
    return dp1(0, a-1, 1) + dp1(a, b-1, 0) + dp1(b, c-1, -1);
}

ll DP[20959000] = {0};
bool DPC[20959000] = {0};

ll dp(int a, int b, int c){
    if(a < 0)return 0;
    int h = enumerate(a,b,c);
    if(DPC[h])return DP[h];
    ll ans1 = A[a][b] + B[a][c] + dp(a-1,b,c);
    ll ans2 = big*big;
    if(b > a+1)ans2 = A[a][a+1] + B[a][b-1] + dp(a-1,a+1,b-1);
    ll ans3 = B[a][a] + dp(a-1, a, a);

    ll ans = ans1;
    ll pek = 0;
    if(ans2 < ans){
        ans = ans2;
        pek = 1;
    }
    if(ans3 < ans){
        ans = ans3;
        pek = 2;
    }

    DPC[h] = 1;
    DP[h] = ans;
    //cerr << a << " " << b << " " << c << "   pek: " << pek << "  ans: " << ans << "\n";
    return ans;
}

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

    //freopen("input.txt","r",stdin);
   // freopen("autput.txt","w",stdout);
    ll a,b,c,d;
    cin >> n;

    rep(c1,0,n){
        rep(c2,0,n-1){
            cin >> a;
            int c3 = c2;
            if(c2 >= c1)c3++;
            M[c1][c3] = a;
        }
    }

    rep(c1,0,n){
        a = 0;
        rep(c2,c1+1,n+1){
            A[c1][c2] = a;
            a += M[c1][c2];
        }
        a = 0;
        per(c2,c1,n){
            B[c1][c2] = a;
            a += M[c2][c1];
        }
    }


    rep(c1,0,n){
        rep(c2,c1,n){
            rep(c3,c2,n){
                dp(c1,c2,c3);
            }
        }
    }

    ll temp = big*big;
    ll extra = 0;
    per(c1,0,n){
        extra += A[c1][n];
        //cerr << dp(c1,c1+1,n-1) << " " << extra << "\n";
        temp = min(temp, dp(c1,c1+1,n-1) + extra);
    }

    cout << temp << "\n";


    return 0;
}


Measured memory_bytes: 192896
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
typedef long long LL;

class LowerEnvelope{ typedef long long LL; int s, t; vector<LL> deq_a; vector<LL> deq_b; inline bool check(LL a1, LL b1, LL a2, LL b2, LL a3, LL b3) const { return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2); } public: LowerEnvelope(int n) : s(0), t(0), deq_a(n), deq_b(n) {} void push(LL a, LL b){ while(s + 1 < t && check(deq_a[t - 2], deq_b[t - 2], deq_a[t - 1], deq_b[t - 1], a, b)) t--; deq_a[t] = a; deq_b[t++] = b; } LL minimum(LL x){ assert(s < t); while(s + 1 < t && deq_a[s] * x + deq_b[s] >= deq_a[s + 1] * x + deq_b[s + 1]) s++; return deq_a[s] * x + deq_b[s]; } }; 
LL INF = 10000000000000000LL;

int main(){
    int N, M, D, X;
    cin >> N >> M >> D >> X;
    vector<int> p(N);
    REP(i, N) cin >> p[i];
    vector<vector<int>> right(D);
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        int x = a;
        int y = abs(b);
        for(int d = 0; d < D; d++){
            right[d].push_back(x - y);
            x += X;
        }
    }
    REP(d, D) sort(right[d].begin(), right[d].end());
    int memo[101][10001];
    memset(memo, -1, sizeof(memo));
    auto w = [&](int d, int i) -> int {
        if(memo[d][i] != -1) return memo[d][i];
        auto itr = lower_bound(right[d].begin(), right[d].end(), p[i]);
        return memo[d][i] = M - (itr - right[d].begin());
    };
    vector<LL> cur(N, INF);
    cur[0] = 0;
    for(int d = 0; d < D; d++){
        vector<LL> next(N, INF);
        LowerEnvelope lowenv(N);
        for(int i = 0; i < N; i++){
            if(cur[i] < INF){
                lowenv.push(w(d, i), cur[i] - (long long)w(d, i) * p[i]);
            }
            next[i] = lowenv.minimum(p[i]);
        }
        cur.swap(next);
    }
    cout << cur[N - 1] << endl;
    return 0;
}

Measured memory_bytes: 10952
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  string S;
  cin >> S;
  if (S.size() != 26) {
    vector<bool> used(26, false);
    for (ll i = 0; i < S.size(); ++i) {
      used.at(S[i] - 'a') = true;
    }
    for (ll i = 0; i < 26; ++i) {
      if (!used.at(i)) {
        S += 'a' + i;
        break;
      }
    }
    cout << S << "\n";
    return 0;
  }
  else {
    vector<bool> can_use(26, false);
    for (ll i = S.size() - 1; i >= 0; --i) {
      if (i == S.size() - 1) {
        can_use.at(S[i] - 'a') = true;
        continue;
      }
      for (ll j = S[i] - 'a' + 1; j < 26; ++j) {
        if (can_use.at(j)) {
          for (ll k = 0; k < i; ++k) {
            cout << S[k];
          }
          cout << (char)('a' + j) << "\n";
          return 0;
        }
      }
      can_use.at(S[i] - 'a') = true;
    }
    cout << -1 << "\n";
  }
}


Measured memory_bytes: 256
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b) {
  return b ? GCD(b,a%b) : a;
}


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll x,y;
  cin>>x>>y;
  ll ans=MOD;
  if(x<=y) ans=min(ans,y-x);
  if(-x<=y) ans=min(ans,y+x+1);
  if(x<=-y) ans=min(ans,-y-x+1);
  if(-x<=-y) ans=min(ans,x-y+2);
  cout<<ans<<endl;
  
  
  
}

Measured memory_bytes: 256
// This is the start of  template//
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long int
#define ll int 
#define vll vector<int>
#define pb push_back
#define pll pair<int,int>
#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
void input(){
#ifndef ONLINE_JUDGE 
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout); 
#endif
}
#define INF LONG_LONG_MAX
#define mod 1000000007
#define array(a,n) vll a(n); rep(i,0,n) cin>>a[i];
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define cases int t; cin>>t; while(t--)
#define printall(a) rep(i,0,a.size()) cout<<a[i]<<" "; cout<<endl;
ll power(ll a,ll n)
{
	if(n==0)
		return 1;
	if(n%2)
	{
		return (a*power((a*a)%mod,n/2))%mod;
	}
	return power((a*a)%mod,n/2);
}
map<int,vector<int>>adj;
map<int,bool>vis;
map<pair<int,int>,int>edge;

int cnt;
void dfs(int u)
{
	vis[u] = true;
	cnt++;
	for(auto child :adj[u])
		if(!vis[child])
			dfs(child);
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  //input();
  int n ,m,ans = 0 ;
  cin>>n>>m;
  for(int i = 0 ;i<m ;i++)
  {
  	int u,v;
  	cin>>u>>v;
  	if(u<v)
  		swap(u,v);
  	if(edge.count({u,v}))
  		continue;
  	edge[{u,v}]++;
  	adj[u].push_back(v);
  	adj[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i)
  {
  		if(!vis[i])
  		{
  			cnt = 0 ;
  			dfs(i);
  			ans = max(ans,cnt);
  		}
  }
  cout<<ans;
}



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

int main( void )
{
    int a,b;
    cin >> a >> b;
    
    int ans = (a + b) % 24;
    cout << ans << endl;
}


Measured memory_bytes: 256