akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
using namespace std;
using ll = long long;
int main(){
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a+b)*h/2 << endl;
    return 0;
}

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

const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); ++i)
#define RFOR(i,n,r) for(ll i = (ll)(n-1); i >= r; --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,n,0)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()

#define cout cout << setprecision(12)

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using vp = vector<pair<ll, ll>>;
using vs = vector<string>;
using vc = vector<char>;
using lst = list<ll>;
using pq = priority_queue<ll>;

template < typename T >
inline void dbg(T a) { cout << a << ' ' << endl; }

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

/*--------------------template--------------------*/

int main() {
    cin >> n;
	int a[n];
	cnt = 1;
	REP(i,n) {
    	cin >> a[i];
    	if (a[i] == cnt) {
        	cnt++;
        } else {
        	ans++;
        }
    }
	if (cnt == 1) { ans = -1; }
    cout << ans << endl;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {
	  public static void main(String args[]){
      	Scanner scan = new Scanner(System.in);
            
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int d = scan.nextInt();
        int cnt;
        
        if( c >= b )cnt = 0;
        else{
          if( a >= c && b <= d )
            cnt = b-a;
          else if( d <= b && a >= c)
            cnt = d-a;
          else if( d <= b && a < c)
            cnt = d-c;
          else
            cnt = b-c;
        }
            
        if( cnt < 0 )cnt = 0;
        System.out.println(cnt);
	  }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
       
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template <typename Monoid>
struct SegmentTree {
  using F = function<Monoid(Monoid, Monoid)>;

  int sz;
  vector<Monoid> seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) { seg[k + sz] = x; }

  void build() {
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a++]);
      if (b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const { return seg[k + sz]; }

  template <typename C>
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while (a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if (check(nxt))
        a = 2 * a + type;
      else
        M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }

  template <typename C>
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if (a <= 0) {
      if (check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) {
        Monoid nxt = f(L, seg[a]);
        if (check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }

  template <typename C>
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if (b >= sz) {
      if (check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for (b += sz; a < b; a >>= 1, b >>= 1) {
      if (b & 1) {
        Monoid nxt = f(seg[--b], R);
        if (check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};

struct Robot {
  int X, D;
  bool operator<(const Robot& that) const { return X < that.X; }
};

int main() {
  const int MOD = 998244353;

  int N;
  cin >> N;
  vector<Robot> R(N);
  for (int i = 0; i < (int)(N); ++i) cin >> R[i].X >> R[i].D;

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

  SegmentTree<int> seg(
      N, [&](int a, int b) { return max(a, b); }, -1e9);
  for (int i = N - 1; i >= 0; --i) {
    int r = distance(R.begin(), lower_bound((R).begin(), (R).end(), Robot{R[i].X + R[i].D, 0}));
    seg.update(i, max(i + 1, seg.query(i + 1, max(r, i + 1))));
  }

  vector<ll> dp(N, -1);
  function<ll(int)> f = [&](int i) {
    if (i == N) return 1ll;
    if (dp[i] != -1) return dp[i];
    return dp[i] = (f(i + 1) + f(seg.query(i, i + 1))) % MOD;
  };

  cout << f(0) << endl;

  return 0;
}


Measured memory_bytes: 30464
# include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,k,i,p=0;
    cin>>k;
    cin>>a>>b;
    for(i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            cout<<"OK";
            p=0;
            break;
        }
        else
        {
            p=1;
        }
    }
    if(p==1)
        cout<<"NG";
    return 0;
}


Measured memory_bytes: 3576
#include<cstdio>
using namespace std;


int main(){
	int count[10001],tmp,num=3;
	for(int i=0;i<10001;i++)count[i]=0;

	for(int i=0;i<10;i++){
		scanf("%d",&tmp);
		count[tmp]++;
	}

	for(int i=10000;i>=0&&num>0;i--){
		if(count[i]>0){
			for(int k=0;k<count[i]&&num>0;k++){
				printf("%d\n",i);
				num--;
			}
		}
	}

    return 0;
}


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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
      
     	Map<String, Word> words = new HashMap<>();
      	for(int i = 0 ; i < n ; i++){
      		String str = sc.next();
      		if(words.containsKey(str)){
      			words.get(str).num++;
      		}else{
      			words.put(str, new Word(str, 1));
      		}
        }
        ArrayList<Word> sortedWords = new ArrayList<>(words.values());
        Collections.sort(sortedWords);
        int maxTimes = sortedWords.get(0).num;

        sortedWords.stream().filter(w -> w.num == maxTimes).forEach(w -> System.out.println(w.str));
    }
}

class Word implements Comparable<Word>{
	String str;
	int num;
	Word(String str, int num){
		this.str = str;
		this.num = num;
	}

	public int compareTo(Word tar){
		int result = tar.num - num;
		if(result == 0){
			result = str.compareTo(tar.str);
		}
		return result;
	}
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int64_t n,k; cin>>n>>k;
	vector<int>v(n+1);
	for(int64_t i=1;i<=n;++i){
		cin>>v.at(i);
	}
	vector<bool>mp(n+1,false); mp.at(1)=true;
	vector<int64_t>cnt(n+1,0);
	int64_t i=1,nw=1,f=1;
	for(;i<=k;++i){
		cnt.at(nw)=i;
		f=nw;
		nw=v.at(nw);
		if(mp.at(nw))break;
		mp.at(nw)=true;
	}
	if(i!=k){
		k=(k-i)%(abs(cnt.at(nw)-cnt.at(f)-1));
		for(int64_t j=0;j<k;++j){
			nw=v.at(nw);
		}
	}
	cout<<nw<<"\n"s;
}

Measured memory_bytes: 5580
#include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <string>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define IREP(it,array) for(vector<int>::iterator it=array.begin(); it!=array.end(); ++it)
#define SREP(it,array) for(vector<string>::iterator it=array.begin(); it!=array.end(); ++it)
#define MP make_pair


int main()
{
  cout.setf(ios::fixed, ios::floatfield);
  cout.precision(10);

  int INF = 1000000;

  int n;
  cin >> n;
  REP(tar,n){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a,a+3);
    if(a[2]*a[2] == a[0]*a[0] + a[1]*a[1])
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }

  return 0;
}

Measured memory_bytes: 1168
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

#define INF 0x3f3f3f3f

using namespace std;

typedef long long LL;
typedef pair<int,int>PII;

const int maxn = 1e5 + 10;

vector<int>G[maxn];

int vis[maxn],cnt[maxn];
int fa[maxn],sz[maxn],deg[maxn];

int ans = 0;

void DFS(int u,int fa) {
	if(vis[u]) return ;
	vis[u] = 1;
	for(int i = 0; i < G[u].size(); i ++) {
		if(G[u][i] != fa && vis[G[u][i]] == 0) {
			ans ++;
			DFS(G[u][i],u);
		}
	}
	return ;
}

int get(int x) {
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}

void Union(int x,int y) {
	int xx = get(x);
	int yy = get(y);
	if(xx == yy) return ;
	fa[yy] = xx;
	sz[xx] += sz[yy];
	return ;
}

int main(void) {
	int n,m,k;
	int u,v;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i ++) {
		fa[i] = i;
		sz[i] = 1;

	}
	for(int i = 1; i <= m; i ++) {
		cin >> u >> v;
//		G[u].push_back(v);
//		G[v].push_back(u);
		deg[u] ++;
		deg[v] ++;
		Union(u,v);
	}
	for(int i = 1; i <= k; i ++) {
		cin >> u >> v;
		if(get(u) == get(v)) {
			cnt[u] --;
			cnt[v] --;
		}
	}
	for(int i = 1; i <= n; i ++) {
		cout << sz[get(i)] - deg[i] + cnt[i] - 1<< " ";
	}
	return 0;
}

Measured memory_bytes: 5376
def main():
    from collections import deque

    X, Y, A, B, C = map(int, input().split())
    *p, = sorted(map(int, input().split()), reverse=True)
    *q, = sorted(map(int, input().split()), reverse=True)
    *r, = sorted(map(int, input().split()), reverse=True)

    p = deque(p[:X])
    q = deque(q[:Y])
    ret = sum(p) + sum(q)
    for x in r:
        if p:
            if q:
                if p[-1] < q[-1]:
                    if p[-1] >= x:
                        break
                    ret += x - p.pop()
                elif p[-1] == q[-1]:
                    popp = True
                    ofs = 1
                    while (1 + ofs) <= len(p) and (1 + ofs) <= len(q):
                        if p[-1 - ofs] == q[-1 - ofs]:
                            ofs += 1
                            continue

                        if p[-1 - ofs] < q[-1 - ofs]:
                            popp = True
                            break

                        if p[-1 - ofs] > q[-1 - ofs]:
                            popp = False
                            break
                    if popp:
                        if p[-1] >= x:
                            break
                        ret += x - p.pop()
                    else:
                        if q[-1] >= x:
                            break
                        ret += x - q.pop()
                else:
                    if q[-1] >= x:
                        break
                    ret += x - q.pop()

            else:
                if p[-1] >= x:
                    break
                ret += x - p.pop()
        else:
            if q:
                if q[-1] >= x:
                    break
                ret += x - q.pop()
            else:
                break

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 106340
n=input()
K=int(input())
m=len(n)

DP=[[[0]*(K+2) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(K+1):
            for k in range(num+1):
                if k==0:DP[i][flag or k<num][j] +=DP[i-1][flag][j]
                else:DP[i][flag or k<num][j] +=DP[i-1][flag][j-1]

print(DP[m][0][K]+DP[m][1][K])

Measured memory_bytes: 3064
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static final int MOD = 998244353;

	static int add(int a, int b) {
		int res = a + b;
		return res >= MOD ? res - MOD : res;
	}

	static int sub(int a, int b) {
		int res = a - b;
		return res < 0 ? res + MOD : res;
	}

	static int mul(int a, int b) {
		int res = (int) ((long) a * b % MOD);
		return res < 0 ? res + MOD : res;
	}

	static int pow(int a, int e) {
		if (e == 0) {
			return 1;
		}
		int r = a;
		for (int i = 30 - Integer.numberOfLeadingZeros(e); i >= 0; i--) {
			r = mul(r, r);
			if ((e & (1 << i)) != 0) {
				r = mul(r, a);
			}
		}
		return r;
	}

	static int inv(int a) {
		return pow(a, MOD - 2);
	}

	static void solve() throws Exception {
		int n = scanInt();
		int m = 1 << n;
		int a[] = new int[m];
		int s = 0;
		for (int i = 0; i < m; i++) {
			s = add(s, a[i] = scanInt());
		}
		for (int i = 0; i < n; i++) {
			int mask = m - 1 - (1 << i);
			for (int j = mask;; j = (j - 1) & mask) {
				int x = a[j], y = a[j + (1 << i)];
				a[j] = add(x, y);
				a[j + (1 << i)] = sub(x, y);
				if (j == 0) {
					break;
				}
			}
		}
		for (int i = 1; i < m; i++) {
			a[i] = mul(mul(m, s), inv(sub(a[i], s)));
		}
		for (int i = 0; i < n; i++) {
			int mask = m - 1 - (1 << i);
			for (int j = mask;; j = (j - 1) & mask) {
				int x = a[j], y = a[j + (1 << i)];
				a[j] = add(x, y);
				a[j + (1 << i)] = sub(x, y);
				if (j == 0) {
					break;
				}
			}
		}
		int norm = inv(m);
		int sub = mul(a[0], norm);
		for (int i = 0; i < m; i++) {
			out.println(sub(mul(a[i], norm), sub));
		}
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

Measured memory_bytes: 47748
#include <bits/stdc++.h>//..1..2..3:Correct:Solved by F2tekkz:)
#define ll long long
#define str string
#define sonic ios_base::sync_with_stdio(0)
using namespace std;
ll n , m , k , i , j , t , q , cnt , cnt1 , cnt2 , cnt3;
ll cnt4 , cnt5 , ans , ans1 , ans2 , ans3 , sum , sum1 , sum2;
ll mini = 1e9 , maxi = -999;
int main(){
	sonic;
	ll a , b , c;
	cin >> a >> b >> c;
	if(a == b || b == c || a == c){
		if((a != b && a == c && b != c) || (a == b && a != c && b != c) || (a != b && a != c && b == c))
			cout << "Yes";
		else
			cout << "No";
	}
	else{
		cout << "No";
	}
}
//     *    *  *  ****    *    *   *
//    *	*   * *   *      * *   *   *
//   *****  **    ****  *****  *****
//   *   *  * *      *  *   *      *
//   *   *  *  *  ****  *   *  *****

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

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



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF INT_MAX
#define endl '\n'
#define ll long long int
#define N 1000005
using namespace std;

inline int redi() {
	int ret = 0,f = 0;char ch = getchar_unlocked();
	while (!isdigit (ch)) {
		if (ch == '-') f = 1;
		ch = getchar_unlocked();
	}
	while (isdigit (ch)) {
		ret = ret*10  + ch - 48;
		ch = getchar_unlocked();
	}
	return f?-ret:ret;
}
inline void print(int x) {
	if(x<0) {putchar_unlocked('-');x=-x;}
	int y=10,len=1;
	while(y<=x)    {y*=10;len++;}
	while(len--){y/=10;putchar_unlocked(x/y+48);x%=y;}
}

inline void init()
{
	ll n;
	cin >> n;
	cout << 3*n*n << endl;
}

inline void solve()
{
}

int main()
{
	//freopen("input.in","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	init();
	solve();
	cout << flush;

	return 0;
}


Measured memory_bytes: 256
import itertools
N = int(input())
xys=[]
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        xy.append(list(map(int,input().split())))
    xys.append(xy)
#print('xys:', xys)  ############


#正直者1,  不親切0
a = [0,1]
Ls = list(itertools.product(a, repeat=N))
#print('Ls:', Ls)  ###########

mujun=[0]*(N+1)
count=0
ans=0
for L in Ls:
    #print('L:        ', L)  ###########
    flag=0
    hito=1
    #count=0
    count=sum(list(L))
    mujun=[0] + list(L)
    for i in L:
        #print('i:', i)    ###########
        if i==1:
            for xy in xys[hito-1]:
                #print('xy:', xy)  #########
                if xy[1] == 1:
                    if mujun[xy[0]]==0:
                        count=0
                        #print('mujuuuuuunnnnnnn!')
                        flag=1
                        break
                    #else:
                        #count+=1
                        #mujun[xy[0]]=1
                else:
                    if mujun[xy[0]]==1:
                        count=0
                        #print('mujuuuuuuuuuuuuuuuuuuuun!')   ###########
                        flag=1
                        break
                    #else:
                        #mujun[xy[0]]=-1


                #print('count:', count)  ###########
                #print('mujun:', mujun)  ###########
        hito+=1
    if flag==0:
        ans=max(ans,count)
    #print('ans:', ans)  ###########

#print('ans:', ans) ###########
print(ans)


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

using namespace std;

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

    int N; cin>>N;
    vector<pair<int,int>> tree[N];
    for (int i = 0; i < N-1; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        u--,v--;
        tree[u].push_back({v,w});
        tree[v].push_back({u,w});
    }
    vector<int> colors(N, -1);
    function<void(int,bool)> coloring = [&](int f, bool b) {
        for (auto path : tree[f]) {
            auto t = path.first;
            if (colors[t] != -1)
                continue;
            colors[t] = path.second % 2 == 0 ? b : !b;
            coloring(t, colors[t]);
        }
    };

    for (int i = 0; i < N; i++) {
        if (tree[i].size() != 1)
            continue;
        coloring(i, 0);
        break;
    }
    for (auto c : colors)
        cout << int(c) << endl;

    
    return 0;
}



Measured memory_bytes: 11648
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int a;
    cin >> a;
    cout << "AB" << char((a/1000) + 67);
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef long long ll;

int main(){
    /*string S;
    cin >> S;
    if(S[2]==S[3]&&S[4]==S[5]) cout << "Yes" << endl;
    else cout << "No" << endl;*/

    int x;
    int happy = 0,temp;
    //bool b = true;
    cin >> x;
    happy += (x/500)*1000;
    x = x%500;
    happy += (x/5)*5;
    cout << happy << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

public class Test
{
	public static void Main()
	{
		 int n = int.Parse(Console.ReadLine());
		 string line = Console.ReadLine();
		 char[] c = line.ToCharArray();
		 int[] W = new int[n+1];
		 int[] E = new int[n+1];
		 W[0] = 0;
		 E[0] = 0;
		 
		 for(int i = 1 ; i < n+1 ; i++){
			 if(c[i-1] == 'W'){
				 W[i] = W[i-1]+1;
				 E[i] = E[i-1];
			 } else {
				 W[i] = W[i-1];
				 E[i] = E[i-1]+1;
			 }
		 }
		 int min = 99999999;
		 int ans = 0;
		 for(int i = 1 ; i < n+1 ; i++){
				ans = W[i-1] + E[n]- E[i];
				if(min > ans){
					min = ans;
				}
		 }
		 Console.WriteLine(min);
	}
}


Measured memory_bytes: 15072
"""
- minでの桁数
- その後の余りでgreedy
- 
"""

num_dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

N, M = list(map(int, input().split()))
t_dic = {}
A = list(map(int, input().split()))
A = sorted(A)[::-1]
for a in A:
    t_dic[a] = num_dic[a]
min_v = min(t_dic.values())

dp = [0] * (N+8)
for i in range(N):
    for a in A:
        num = t_dic[a]
        if i !=0 and dp[i] == 0:
            continue
        dp[i+num] = max(10 * dp[i]+ a, dp[i+num])

print(dp[N])

Measured memory_bytes: 14836
# ABC 164 E 草案
import sys
sys.setrecursionlimit(10**6)

n,m,s= map(int, input().split())
g= [list(map(int, input().split())) for i in range(m)]
# 両替所
c= [list(map(int, input().split())) for i in range(n)]

x=2501
# 作るグラフ (辺*所有銀貨,必要時間)
gg=[[] for i in range(n*x)]
for i in range(n):
    for j in range(x-1):
        # 金貨を銀貨に交換
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i*x+j].append((i*x+y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        # 銀貨足りる時移動できる
        if i-a>=0:
            gg[v*x+i].append((u*x+i-a,b))
            gg[u*x+i].append((v*x+i-a,b))




#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance
s=min(s,2500)
ans=dijkstra(gg,n*x,s)

for i in range(1, n):
    print(min(ans[x * i:x * (i + 1)]))

Measured memory_bytes: 119000
#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  
#include <numeric>
#include <sys/resource.h>
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define endl '\n'
using ll = long long;
 
const int precision = 15;
const int modulo =  1000000007; // 10^9 + 7
const ll lmodulo =  1000000007; // 10^9 + 7
 
const double EPS = 1e-9;
const ll inf = 1e18;


void increaseStack() {
	const rlim_t kStackSize = 50 * 1024 * 1024;   // min stack size = 50 MB
	struct rlimit rl;
	int result;

	result = getrlimit(RLIMIT_STACK, &rl);
	if (result == 0) {
		if (rl.rlim_cur < kStackSize) {
			rl.rlim_cur = kStackSize;
		    result = setrlimit(RLIMIT_STACK, &rl);
		    if (result != 0) {
		    	fprintf(stderr, "setrlimit returned result = %d\n", result);
		    }
		}
	}
}


ll rec(int l, int r,  vector<int> & values, vector<vector<ll>> & memo) {
	if (l >= r) return 0;
	if (r - l == 1) return values[l] + values[r];
	if (memo[l][r] != -1) return memo[l][r];
	
	ll acc = inf;
	ll curAcc = accumulate(values.begin() + l, values.begin() + r + 1, 0l); 
	for (auto k = l; k < r; ++k) {
		acc = min(acc, rec(l, k, values, memo) + rec(k + 1, r, values, memo));
	}
	acc += curAcc;
	memo[l][r] = acc;
	return acc;
}

void solve_rec() {
	int n; cin >> n;
	vector<int> values(n);
	for (auto &it : values) cin >> it;

	vector<vector<ll>> memo(n + 1, vector<ll>(n + 1, -1));
	ll ret = rec(0, values.size() - 1, values, memo);
	cout << ret;
}

void solve() {
	int n; cin >> n;
	vector<ll> values(n);
	for (auto &it : values) cin >> it;

	vector<ll> accValues = values;
	for (auto i = 1; i < accValues.size(); ++i) {
		accValues[i] += accValues[i - 1];
	} 

	vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, inf));

	for (auto i = 0; i < n; ++i) {
		dp[i][i] = 0;
	}

	for (auto d = 1; d < n; ++d) {
		for (auto l = 0; l + d < n; ++l) {
			auto r = l + d;

			ll curAcc = accValues[r];
			curAcc -= l - 1 >= 0 ? accValues[l - 1] : 0;
			for (auto k = l; k < r; ++k) {
				dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + curAcc);
			}
		}
	}

	cout << dp[0][n - 1];
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(precision);
  cout.setf(ios_base::fixed);
  solve();
  return 0;
}


Measured memory_bytes: 1536
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  long N;
  cin >> N;
  
  vector<long> nums(N);
  for (long n = 0; n < N; ++n) cin >> nums[n];
  bool res = true;
  for (long i = N-1; i > 0; --i) {
    if (nums[i] - nums[i-1] < 0) {
      --nums[i-1];
      if (nums[i] != nums[i-1]) {
        res = false;
        break;
      }
    }
  }
  cout << (res ? "Yes" : "No") << endl;
  
  return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <locale>
#include <iomanip>

#define nl '\n';

using namespace std;

int n;
string s;

int main(){

    cin >> s;

    for(int i = 0; i < s.length(); i++){
        if(s[i] == '+'){
            n++;
        } else if(s[i] == '-'){
            n--;
        }
    }

    cout << n;



    



}

//g++ -std=c++14 comp.cpp -o b; ./b.exe
//g++ -std=c++14 comp.cpp && ./a.out

// char** arr = new char*[r];
// for(long long i = 0; i < r; i++) arr[i] = new char[c];

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 100000000;
const int MAX_N = 100;
typedef pair<int , int> P;
typedef long long ll;
 
int main () {
  int A, B;
  cin >> A >> B;
  int ans = A * B;
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 3768
from sys import stdin
 
input_num = stdin.readline().strip().split(" ")

X = int(input_num[0])
Y = int(input_num[1])
if Y % 2 != 0:
  print("No")
else:
  if X * 4 < Y:
    print("No")
  elif X * 2 > Y:
    print("No")
  else:
    print("Yes")

Measured memory_bytes: 9108
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int main(){
	int A, B, C;
	cin>> A >> B >> C;
	int modulo = C % B;
	for (int i = 1; i <= 1000; i++){
		if ((A % B) * (i % B) % B == C % B){
			cout<< "YES" <<endl;
			return 0;
		}	
	}
	cout<< "NO" <<endl;
	return 0;	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 100000009;
const int INF = 1e9;
const ll INFLONG = 1e18;

int main(){
  ll a;
  double b;
  ll c;
  cin >> a >> b;
  c = (ll)(b * 100.0001);
  cout << a * c / 100;
}

Measured memory_bytes: 3716
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N,Q = imn()
S = input()
lr = [iln() for _ in range(Q)]

s = [0 for _ in range(N+1)]

for i in range(N):
    s[i+1] = s[i]
    if i+1 < N and S[i] == 'A' and S[i+1] == 'C': s[i+1] += 1 

for i in range(Q):
    l = lr[i][0]
    r = lr[i][1]
    print(s[r-1]-s[l-1])


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

int main(){
    long long n, m, k;
    cin >> n >> m >> k;
    vector<long long> a(n);
    vector<long long> b(m);
    for(int i=0; i<n; i++){
        cin >> a.at(i);
    }
    for(int i=0; i<m; i++){
        cin >> b.at(i);
    }
    vector<long long> A;
    vector<long long> B;
    A.push_back(0);
    B.push_back(0);
    for(int i=0; i<n; i++){
        A.push_back(A.at(i)+a.at(i));
    }
    for(int i=0; i<m; i++){
        B.push_back(B.at(i)+b.at(i));
    }

    int ans = 0, j = m;
    for(int i=0; i<=n; i++){
        if(A.at(i) > k){
            break;
        }
        while(B.at(j) > k - A.at(i)){
            j--;
        }
        ans = max(ans, i+j);
    }
    cout << ans << endl;
    return 0;
    
}

Measured memory_bytes: 11116
n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")

Measured memory_bytes: 9180
#include<cstdio>
#define maxn 100005
#define mod 1000000007
int n,a[maxn],pre[maxn],deg[maxn],cnt[maxn],f[maxn],ans=1;
bool vis[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) { scanf("%d",&a[i]); deg[a[i]]++; }
	for(int i=1;i<=n;i++)
	{
		if(deg[i]>2) { printf("0\n"); return 0; }
		if(deg[i]<2||vis[i]) continue;
		int p=i;
		do
		{
			if(vis[p]) { printf("0\n"); return 0; }
			vis[p]=true,pre[a[p]]=p,p=a[p];
		}while(p!=i);
	}
	for(int i=1;i<=n;i++)
		if(!deg[i])
		{
			int p=i,l1=0,l2=0;
			while(!vis[p]) vis[p]=true,p=a[p],l1++;
			do l2++,p=pre[p]; while(deg[p]!=2);
			if(l1<l2) ans=ans*2%mod;
			else if(l1>l2) { printf("0\n"); return 0; }
		}
	for(int i=1;i<=n;i++)
		if(!vis[i])
		{
			int p=i,l=0;
			do l++,p=a[p],vis[p]=true; while(p!=i);
			cnt[l]++;
		}
	for(int i=1;i<=n;i++)
	{
		int mul=1;
		if(i!=1&&(i&1)) mul++;
		f[0]=1,f[1]=mul;
		for(int j=2;j<=cnt[i];j++) f[j]=(1ll*f[j-2]*(j-1)%mod*i%mod+1ll*f[j-1]*mul%mod)%mod;
		ans=1ll*ans*f[cnt[i]]%mod;
	}
	printf("%d\n",ans);
}

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

const int MAX_NODE = 100;

int main() {
	int nodes[MAX_NODE + 1];
	int last = 0, from, to;
	memset(nodes, 0, sizeof(nodes));
	
	while (cin >> from >> to) {
		if (from == 0 && to == 0) {
			if ((nodes[1] & 1) && (nodes[2] & 1)
					&& all_of(nodes + 3, nodes + last + 1,
						[](int i){return !((i) & 1);})) {
				cout << "OK" << endl;
			}
			else {
				cout << "NG" << endl;
			}
			
			last = 0;
			memset(nodes, 0, sizeof(nodes));
		}
		else {
			nodes[from]++;
			nodes[to]++;
			last = max(last, max(from, to));
		}
	}
	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {

fast();

{
  map<string,int >m;
  //pair<int,string,>p;
  ll n;
  cin>>n;
    vector<string>v;
  for(int i=1;i<=n;i++)
  {
       string s;
       cin>>s;
       m[s]++;
       

  }
int max=0;
  for(auto it:m)
  {
    if(max<it.se)
    {
      max=it.se;
    }
  }
  for(auto it:m)
  {
    if(it.se==max)
    {
      v.pb(it.fi);
    }
  }
  sort(v.begin(),v.end());
  for(auto it:v)
  {
    cout<<it<<endl;
  }

}
return 0;
}


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

const int maxn = 1e5 + 5;
int H[maxn];

int main() {

	int N;
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
        scanf("%d", H+i);
	for(int i = N-1; i; i--)
        if(H[i-1]-H[i] > 1) {
            printf("No");
            return 0;
        }
        else if(H[i-1]-H[i] == 1) H[i-1]--;
	printf("Yes");
    return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long L,R;
	cin >> L>>R;
	long long ans = (L * (L + 1) % 2019);
	for (long long l = L;l<R;++l) {
		for (long long r = l + 1;r<=R;++r) {
			if (0 == l * r % 2019) {
				cout << 0 <<  endl;
				return 0;
			}
			ans = min(ans, (l*r)%2019);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3616
defmodule Main do
  def main do
    n = IO.gets("") |> String.trim() |> String.to_integer()

    ans =
      case rem(n, 10) do
        3 -> "bon"
        0 -> "pon"
        1 -> "pon"
        6 -> "pon"
        8 -> "pon"
        _ -> "hon"
      end

    IO.puts(ans)
  end
end


Measured memory_bytes: 30652
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
typedef pair<int,int> pii;
#define N 300005
const int B=10;
int v[N],w[N],n,tot;
int dep[N];
map<int,int> f[1<<B];
map<int,int> tmp;
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) v[i]=read(),w[i]=read();
	dep[1]=1; for(int i=2;i<=n;i++) dep[i]=dep[i/2]+1;
	for(int i=1;i<=n;i++)
	{
		if(dep[i]<=B)
		{
			f[i]=f[i/2];
			for(auto [x,y]:f[i/2])
			{
				if(x+w[i]<=100000) f[i][x+w[i]]=max(f[i][x+w[i]],y+v[i]);
			}
			f[i][w[i]]=max(f[i][w[i]],v[i]);
			int cur=0; vector<map<int,int>::iterator> v;
			for(auto j=f[i].begin();j!=f[i].end();++j)
			{
				cur=max(cur,(*j).sec);
				if((*j).sec!=cur) v.pb(j);
			}
			for(auto j:v) f[i].erase(j);
		}
	}
	// for(int i=1;i<=n;i++)
	// {
		// if(dep[i]>B) break;
		// cout<<i<<" :\n";
		// for(auto [x,y]:f[i]) printf("%d %d\n",x,y);
	// }
	int Q=read();
	while(Q--)
	{
		int u=read(),L=read();
		int r=dep[u];
		if(r<B)
		{
			auto x=f[u].upper_bound(L);
			if(x==f[u].begin()) printf("0\n");	
			else x--,printf("%d\n",(*x).sec);
		}
		else
		{
			// map<int,int> res; res.clear();
			int fa=u;
			while(dep[fa]>B) fa/=2;
			vector<pii> t;
			int tmp=u;
			while(tmp!=fa)
			{
				t.eb(v[tmp],w[tmp]);
				// map<int,int> qaq=res;
				// for(auto [x,y]:res)
				// {
					// if(x+w[tmp]<=100000) qaq[x+w[tmp]]=max(qaq[x+w[tmp]],y+v[tmp]);
				// }
				// qaq[w[tmp]]=max(qaq[w[tmp]],v[tmp]);
				// res=qaq;
				// int cur=0; vector<map<int,int>::iterator> v;
				// for(auto j=res.begin();j!=res.end();++j)
				// {
					// cur=max(cur,(*j).sec);
					// if((*j).sec!=cur) v.pb(j);
				// }
				// for(auto j:v) res.erase(j);
				tmp/=2;
			}
			// for(auto [x,y]:f[fa]) printf("%d %d\n",x,y); cout<<"\n";
			// for(auto [x,y]:res) printf("%d %d\n",x,y); cout<<"\n";
			int ans=0;
			auto x=f[fa].upper_bound(L);
			if(x==f[fa].begin()) ans=0;
			else x--,ans=(*x).sec;
			for(int i=0;i<(1<<(int)t.size());i++)
			{
				int x=0,y=0;
				for(int j=0;j<(int)t.size();j++)
				{
					if(i&(1<<j)) x+=t[j].sec,y+=t[j].fir;
				}
				int ned=L-x;
				if(ned<0) continue;
				auto rr=f[fa].upper_bound(ned);
				if(rr==f[fa].begin()) ans=max(ans,y);
				else rr--,ans=max(ans,y+(*rr).sec);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}




Measured memory_bytes: 37884
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = read().rstrip()

T = S[::-1]

L = (len(S) + 1) // 2

answer = sum(x != y for x,y in zip(S[:L],T[:L]))
print(answer)

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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; }

int main() {
  int N;
  cin >> N;
  map<int, int> mp;
  rep(i, N) {
    int tmp;
    cin >> tmp;
    mp[tmp]++;
  }
  if (mp.size() > 3)
    cout << "No" << endl;
  else if (mp.size() == 3 && !(N%3)) {
    vector<int> a;
    for (auto e : mp) {
      if (e.second != N/3) {
        cout << "No" << endl;
        return 0;
      }
      a.push_back(e.first);
    }
    if (!(a[0]^a[1]^a[2]))
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  } else if (mp.size() == 2 && !(N%3)) {
    if (mp[0] == N/3)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  } else if (mp[0] == N)
    cout << "Yes" << endl;
  else
    cout << "No" << endl; 
  return 0;
}

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

namespace AtCoder_Project_CSharp
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            bool f = false;
            foreach (var c in s)
            {
                if(f)
                {
                    if(c=='C')
                    {
                        Console.WriteLine("Yes");
                        return;
                    }
                    f = false;
                }
                if(c=='A')
                {
                    f = true;
                }
                else
                {
                    f = false;
                }
            }
            Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define mp make_pair

using namespace std;
const int N = 3e5 + 5, MI = 1e6;
int read() {
	static streambuf* in = cin.rdbuf();
	#define gc (p1 == p2 && (p2 = (p1 = buf) + in -> sgetn(buf, MI), p1 == p2) ? -1 : *p1++)
	static char buf[MI], *p1, *p2;
	int c = gc, r = 0;
	while(c < 48) c = gc;
	while(c > 47) r = (r << 3) + (r << 1) + (c & 15), c = gc;
	return r;
}
int h, w, m, ans, cx[N], st[N][20], lg[N];
vector <int> p[N];
int qry(int l, int r) {
	int t = lg[r-l+1];
	return max(st[l][t], st[r-(1<<t)+1][t]);
}
int main() {
	#ifdef local
		freopen("in.txt", "r", stdin);
	#endif
	ios::sync_with_stdio(0), cin.tie(0);
	cin>>h>>w>>m;
	rep(i, 2, w) lg[i] = lg[i>>1] + 1;
	while(m--) {
		int x = read(), y = read();
		cx[x]++, st[y][0]++, p[x].push_back(y);
	}
	rep(i, 1, 19) rep(j, 1, w - (1 << i) + 1)
		st[j][i] = max(st[j][i-1], st[j+(1<<(i-1))][i-1]);
	rep(i, 1, h) {
		sort(p[i].begin(), p[i].end());
		int pos = 1, sz = p[i].size();
		rep(j, 0, sz - 1) {
			ans = max(ans, cx[i] + st[p[i][j]][0] - 1);
			if(pos < p[i][j]) ans = max(ans, cx[i] + qry(pos, p[i][j] - 1));
			pos = p[i][j] + 1;
		}
		if(pos <= w) ans = max(ans, cx[i] + qry(pos, w));
	}
	return !(cout << ans);
}

Measured memory_bytes: 46748
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = -1*((1LL<<63)+1);
const int inf = -1*((1<<31)+1);

using namespace std;
const int MAX = 1000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vector<int> cnt(1e5+1);
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(20);
    COMinit();

    int n;
    cin >> n;
    vector<int> a(n+1);
    int l,r;
    int x;
    rep(i,n+1){
        cin >> a[i];
        cnt[a[i]]++;
        if(cnt[a[i]]==2){
            x = a[i];
            r = i;
        }
    }
    rep(i,n+1){
        if(x==a[i]){
            l = i;
            break;
        }
    }
    // まずどの数は重複しているかを調べる 
    // と思ったけど大事なのは数値じゃなくて、出現した位置
    rep(i,n+1){ 
        // 長さ i + 1 の数列を作る
        int now = i + 1;
        ll ans = 0;
        // まずは全ての要素が異なる長さ n の数列として考えて個数を出す
        // n 個の中から i+1個選ぶので
        ans =  (COM(n+1,now)) + mod;
        ans -= COM(l  + n - r,now-1);
        cout << ans % mod << endl;
    }
}

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    double a,b,C;
    cin >> a >> b >> C;
    C=C*M_PI/180.0;
    printf("%.12lf\n%.12lf\n%.12lf\n",0.5*a*b*sin(C),a+b+sqrt(a*a+b*b-2*a*b*cos(C)),b*sin(C));
    
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
//#define DEBUG
#ifdef DEBUG
#define DEBUG_PRINT(fm, ...) do{std::printf("%s:%d(%s)", __FILE__, __LINE__, __func__);std::cout << "DEBUG PRINT ";std::printf(fm, __VA_ARGS__);}while(0)
#define DEBUG_VAL(a, b) do{std::printf("%s:%d(%s)", __FILE__, __LINE__, __func__);std::cout <<"DEBUG VAL " << a << ":" << b << endl;}while(0)
#else
#define DEBUG_PRINT(...)do{}while(0);
#define DEBUG_VAL(a, b)do{}while(0);
#endif

using namespace std;
using ll = long long;
using v1 = vector<int>;
using vl = vector<long long>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;
int main(){
    int n,m;
    cin >> n >> m;
    priority_queue<ll> A;
    rep(i, n){
        ll a;
        cin >> a;
        A.push(a);
    }
    rep(i, m){
        ll a = A.top();
        A.pop();
        a /= 2;
        A.push(a);
    }
    ll ans = 0;
    while(!A.empty()){
        ans += A.top();
        A.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 4280
def main():
    n, k = map(int, input().split(' '))
    mx = (n - 1) * (n - 2) / 2
    if k > mx:
        print(-1)
        exit()
    ans = []
    for i in range(2,n+1):
        ans.append((1,i))
    if len(ans) < n-1+mx-k:
        for i in range(2,n+1):
            if i+1 < n+1:
                for j in range(i+1,n+1):
                    ans.append((i,j))
                    if len(ans) >= n-1+mx-k:
                        break
                if len(ans) >= n-1+mx-k:
                    break
    print(int(n-1+mx-k))
    for i,j in ans:
        print(i,j)

main()


Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int i;
    cin>>s;
    for (i=0;i<s.length();i++)
    if (s[i]!=',') cout<<s[i];
    else cout<<' ';
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
if n == 10 or n == 10 ** 2 or n == 10 ** 3 or n == 10 ** 4 or n == 10 ** 5:
    print(10)
else:
    ans = 0
    a = str(n)
    for i in range(len(a)):
        ans += int(a[i])
    print(ans)

Measured memory_bytes: 9176
/*
sonu_verma1
*/
#include <bits/stdc++.h>
// For policy based data structure
/*#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> */
using namespace std;
/*using namespace __gnu_pbds; 
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set;*/
 
#define MD 1000000007
#define X first
#define Y second
#define pb push_back
#define debug(val, ch) cout <<val <<ch
#define FOR(i, st, en, ch) for(register int i = (st); i <= (en) ; i += (ch))
#define RFOR(i, st, en, ch) for(register int i = (st); i >= (en) ; i -= (ch))
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
 
typedef long long int ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
typedef pair<bool, int> pbi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
/*********************************************************************/
void test(int r)
{
    ll n,W,V=0;
    cin>>n>>W;
    vector<int>w(n),v(n);
    int i,j;
    for(i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
        V+=v[i];
    }
    vector<ll>dp(V+1,INT_MAX);
    dp[0]=0;
    for(i=0;i<n;i++)
    {
        for(j=V;j>=1;j--)
        {
            if(j-v[i]>=0)
            {
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
            }
        }
    }
    int ans=0;
    for(i=1;i<=V;i++)
    {
        if(dp[i]<=W)
            ans=i;
    }
    cout<<ans<<endl;

    

}
/***********************************************************************/
int main()
{
    fast();
    int t=1,r;
    // cin>>t;
    for(r=1;r<=t;r++)
        test(r);
    return 0;
}

Measured memory_bytes: 3968
using System;
using System.Collections.Generic;
using System.Linq;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine((r[0] - 1) * (r[1] - 1));
        }        
        
    }
}

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

using namespace std;

typedef long long int	lli;
const int N = (int) 1e5 + 10;
int isPrime[N];
int pre[N];

void build(){
	for(lli i = 2 ; i < N ; i++){
		if(!isPrime[i]){
			for(lli j = i * i ; j < N ; j += i){
				isPrime[j] = 1;
			}
		}
	}
}

int main (){
	build();


	int q;
	
	for(int i = 2 ; i < N ; i++){
		if(i % 2 != 0 && !isPrime[i] && !isPrime[(i + 1) / 2]){
			pre[i] = 1;
		}
		
		pre[i] += pre[i - 1];
	}

	scanf("%d", &q);
	
	while(q--){
		int l, r;

		scanf("%d%d", &l, &r);
	
		printf("%d\n", pre[r] - pre[l - 1]);
	}

	return 0;	
}

Measured memory_bytes: 1408