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

bool prime[N+5];
int C[N+5];

void seive(){
    memset(prime,true,sizeof(prime));
    prime[1]=false;
    for(int i=4;i<=N;i+=2) prime[i]=false;
    for(int i=3;i<=sqrt(N);i+=2){
        if(prime[i])
            for(int j=i*i;j<=N;j+=2*i)
                prime[j]=false;
    }
    //for(int i=1;i<N;i++) if(prime[i]) cout<<i<<endl;
    int c=0;
    for(int i=1;i<=N;i++){
        if(prime[i]) c++;
        C[i]=c;
        //cout<<C[i]<<endl;
    }
}

int main(){

    seive();
    int x;
    while(scanf("%d",&x)==1)
        printf("%d\n",C[x]);
}

Measured memory_bytes: 8100
import java.util.Scanner;

class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    while(true){
      int H = sc.nextInt();
      int W = sc.nextInt();
      if(H == 0 && W == 0){
        break;
      }
      for(int x = 0; x < H; x++){
        for(int y = 0; y < W; y++){
          if(x == 0 || y == 0 || x == H-1 || y == W-1){
            System.out.print("#");
          }else{
            System.out.print(".");
          }
        }
        System.out.println("");
      }
      System.out.println("");
    }
  }
}



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

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

int main(void){

	int A = 0;
	int x[10005] = {0};

	while(1){
		cin >> x[A];
		if(x[A] == 0) break;
		A++;
	}

	rep(i,A){
		cout << "Case "<< i + 1 << ": " << x[i] << "\n";
	}
}

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

typedef long long ll;

const int MAX_N = 100001;

ll st[1 << 18];

void init(int n){
    int nn = 1;
    while(nn < n) nn *= 2;
    fill(st, st + 2 * nn - 1, 0);
}

void add(int i, ll x, int k, int l, int r){
    if(i < l || r <= i) return;
    if(r - l == 1) st[k] += x;
    else{
        int chl = 2 * k + 1;
        int chr = 2 * k + 2;
        add(i, x, chl, l, (l + r) / 2);
        add(i, x, chr, (l + r) / 2, r);
        st[k] = st[chl] + st[chr];
    }
}

ll get_sum(int a, int b, int k, int l, int r){
    if(r <= a || b <= l) return 0LL;
    if(a <= l && r <= b) return st[k];
    ll res_l = get_sum(a, b, 2 * k + 1, l, (l + r) / 2);
    ll res_r = get_sum(a, b, 2 * k + 2, (l + r) / 2, r);
    return res_l + res_r;
}

int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    init(++n);
    for(int _ = 0; _ < q; ++_){
        int c, x, y;
        scanf("%d%d%d", &c, &x, &y);
        if(c == 0){
            add(x, y, 0, 0, n);
        }else{
            ll ret = get_sum(x, y + 1, 0, 0, n);
            printf("%lld\n", ret);
        }
    } 
    return 0;
}

Measured memory_bytes: 3236
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    string ss,ts;
    vector<char> sv,tv;
    cin>>ss>>ts;
    for(auto sc : ss){
        sv.push_back((sc));
    }
    for(auto tc : ts){
        tv.push_back(tc);
    }

    //sv sort
    bool flag=false;
    vector<int> sort_s;
    sort_s.push_back(0);
    for(int n=1;n<sv.size();++n){
        flag=false;
        for(int m=0;m<sort_s.size();++m){

            if(string(1, sv.at(sort_s.at(m)) ) > string(1,sv.at(n)) ){
                sort_s.insert(sort_s.begin() + m , n);
                flag=true;
                break;
            }

        }
        if(!flag)sort_s.push_back(n);
    }

    vector<int> sort_t;
    sort_t.push_back(0);
    for(int n=1;n<tv.size();++n){
        flag=false;
        for(int m=0;m<sort_t.size();++m){

            if(string(1, tv.at(sort_t.at(m)) ) < string(1,tv.at(n)) ){
                sort_t.insert(sort_t.begin() + m , n);
                flag=true;
                break;
            }

        }
        if(!flag)sort_t.push_back(n);
    }

    string ta , sa;
    for(auto tes:sort_s)sa.push_back( sv.at(tes));
    for(auto tes:sort_t)ta.push_back(tv.at(tes));

    cout << (sa < ta?"Yes":"No")<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>

#define MAXN 100000
int N;
long long A[MAXN+5],B[MAXN+5];

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%lld%lld",&A[i],&B[i]);
    long long Ans=0;
    for(int i=N;i>=1;i--){
        A[i]+=Ans;
        Ans+=(B[i]-(A[i]%B[i]))%B[i];
    }
    printf("%lld",Ans);
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back

main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int p,q,r;
	cin>>p>>q>>r;

	cout<<p+q+r-max({p,q,r});	
}

Measured memory_bytes: 256
type point = Pt of float * float

let edge_length (Pt (x1, y1)) (Pt (x2, y2)) =
  let square x = x *. x in
  sqrt @@ (square (x1 -. x2)) +. (square (y1 -. y2))

let edge_lengths p1 p2 p3 =
  (edge_length p2 p3), (edge_length p3 p1), (edge_length p1 p2)

let add_vector (Pt (x1, y1)) (Pt (x2, y2)) = Pt (x1 +. x2, y1 +. y2)

let mul_vector s (Pt (x, y)) = Pt (s *. x, s *. y)

let area p1 p2 p3 =
  let a, b, c = edge_lengths p1 p2 p3 in
  let s = (a +. b +. c) /. 2. in
  sqrt @@ s *. (s -. a) *. (s -. b) *. (s -. c)

let center p1 p2 p3 =
  let a, b, c = edge_lengths p1 p2 p3 in
  let a2, b2, c2 = a *. a, b *. b, c *. c in
  let s = area p1 p2 p3 in
  let nom = 16. *. s *. s in
  add_vector
    (mul_vector (a2 *. (b2 +. c2 -. a2) /. nom) p1)
    (add_vector
       (mul_vector (b2 *. (c2 +. a2 -. b2) /. nom) p2)
       (mul_vector (c2 *. (a2 +. b2 -. c2) /. nom) p3))

let radius p1 p2 p3 =
  let a, b, c = edge_lengths p1 p2 p3 in
  let den =
    sqrt @@ (a +. b +. c) *. (~-.a +. b +. c) *. (a -. b +. c) *. (a +. b -. c) in
  (a *. b *. c) /. den

let read_lines n =
  let rec read_lines n acc =
    if n = 0 then List.rev acc
    else read_lines (pred n) ((read_line ())::acc) in
  read_lines n []

let solve line =
    Scanf.sscanf
      line "%f %f %f %f %f %f"
      begin
        fun x1 y1 x2 y2 x3 y3 ->
        let p1, p2, p3 = Pt (x1, y1), Pt (x2, y2), Pt (x3, y3) in
        let Pt (xc, yc) = center p1 p2 p3 in
        let radius = radius p1 p2 p3 in
        Printf.printf "%.3f %.3f %.3f\n" xc yc radius
      end

let () =
  let num_lines = int_of_string (read_line ()) in
  List.iter solve (read_lines num_lines)

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

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

  int ans;
  for (int i = 1; i <= 9; i++) {
    ans = i*100 + i*10 + i;
    if (ans >= N) break;
  }

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

Measured memory_bytes: 256
a, b, c, d = map(int, input().split())

temp_1 = a * c
temp_2 = a * d
temp_3 = b * c
temp_4 = b * d

maxv = temp_1
if temp_2 > maxv:
    maxv = temp_2
if temp_3 > maxv:
    maxv = temp_3
if temp_4 > maxv:
    maxv = temp_4

print(maxv)


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

int main(){
	int n, m, ans;
	cin >> n >> m;
	ans = m;
	for(int i=0 ; i < n ; i++ ){
		int a, b;
		cin >> a >> b;
		m = m + a - b;
		if( m < 0 ){
			cout << 0 << endl;
			return 0;
		}
		ans = max(ans, m);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1160
a, b = gets.chomp.split.map(&:to_i)
flag = false
money = 0
price = []
if a.even?
  aprice_low = a * 25 / 2
  (0..12).each do |i|
    price.push(aprice_low + i)
  end
else
  aprice_low = a * 25 / 2 + 1
  (0..11).each do |i|
    price.push(aprice_low + i)
  end
end

bprice_low = b * 10

(0..9).each do |i|
  if price.include?(bprice_low + i)
    money = bprice_low + i
    flag = true
    break
  end
  price.push(bprice_low + i)
end

if flag
  puts money
else
	puts -1
end

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

long long mod_pow(long long x, long long n){
    if(n == 0) return 1;
    long long res = mod_pow(x*x % mod, n / 2);
    if(n & 1) res = res*x % mod;
    return res;
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n), c(n);
    rep(i, 0, n){
        cin >> a[i];
        c[a[i]]++;
    }
    bool f = true;
    rep(i, 0, n){
        if(n % 2){
            if(i % 2){
                if(c[i] != 0) f = false;
            }else{
                if(i == 0){
                    if(c[i] != 1) f = false;
                }else{
                    if(c[i] != 2) f = false;
                }
            }
        }else{
            if(i % 2){
                if(c[i] != 2) f = false;
            }else{
                if(c[i] != 0) f = false;
            }
        }
    }
    
    if(!f) cout << 0 << endl;
    else cout << mod_pow(2, n / 2) << endl;
}

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

class B
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var ss = new int[n].Select(_ => Console.ReadLine()).OrderBy(s => s.Length).ToArray();

		var r = 0L;
		var root = new Node();

		foreach (var s in ss)
		{
			var node = root;
			for (int i = s.Length - 1; i >= 0; i--)
			{
				if (i == 0)
					if (node.Ends.ContainsKey(s[i])) node.Ends[s[i]]++;
					else node.Ends[s[i]] = 1;
				else
					foreach (var (c, v) in node.Ends)
						if (s.IndexOf(c, 0, i + 1) >= 0) r += v;

				if (!node.Nexts.ContainsKey(s[i]))
					node.Nexts[s[i]] = new Node();
				node = node.Nexts[s[i]];
			}
		}

		Console.WriteLine(r);
	}
}

class Node
{
	public Dictionary<char, int> Ends = new Dictionary<char, int>();
	public Dictionary<char, Node> Nexts = new Dictionary<char, Node>();
}


Measured memory_bytes: 398096
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		
		if((A < C && C < B) || (A > C && C > B)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		
	}
}


Measured memory_bytes: 22740
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005,M=1e9+7;
int f[N],w[N],c[N],n,X,Y,fac[N],inv[N];
vector<int> p[N],v[N];
int find(int x){
	if (x==f[x])return x;
	return f[x]=find(f[x]);
}
int cmp(int x,int y){
	return w[x]<w[y];
}
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans;	
}
signed main(){
	scanf("%lld%lld%lld",&n,&X,&Y);
	for (int i=1;i<=n;i++)scanf("%lld%lld",&c[i],&w[i]),v[c[i]].push_back(i);
	for (int i=1;i<=n;i++)sort(v[i].begin(),v[i].end(),cmp);
	int now1=0,now2=0;w[0]=1e9+1;
	for (int i=1;i<=n;i++)f[i]=i;
	for (int i=1;i<=n;i++)
		if (v[i].size()){
			if (w[v[i][0]]<w[now2])now2=v[i][0];
			if (w[now1]>w[now2])swap(now1,now2);
		}
	for (int i=1;i<=n;i++)
		for (int j=1;j<v[i].size();j++)	
			if (w[v[i][j]]+w[v[i][0]]<=X)f[find(v[i][j])]=find(v[i][0]);
	for (int i=1;i<=n;i++){
		if (c[now1]!=c[i]){
			if (w[now1]+w[i]<=Y)f[find(i)]=find(now1);
		}
		else if (now2)
			if (w[now2]+w[i]<=Y)f[find(i)]=find(now2);
	}
	int ans=1;
	fac[0]=inv[0]=1;
	for (int i=1;i<=n;i++)fac[i]=fac[i-1]*i%M,inv[i]=ksm(fac[i],M-2);
	for (int i=1;i<=n;i++)p[find(i)].push_back(c[i]);
	for (int i=1;i<=n;i++)
		if (find(i)==i){
			sort(p[i].begin(),p[i].end());
			(ans*=fac[p[i].size()])%=M;
			for (int j=0,k=0;j<p[i].size();j=k){
				while (k<p[i].size()&&p[i][j]==p[i][k])k++;
				(ans*=inv[k-j])%=M;
			}
		}
	printf("%lld\n",ans);	
	return 0;
}

Measured memory_bytes: 27520
#include<stdio.h>
int main(void){
	int a, b;
  
  scanf("%d %d", &a, &b);
  
  if(a > 12){
  	printf("%d\n", b);
  }
  else if(a < 6){
  	printf("0\n");
  }
  else{
  	printf("%d\n", b / 2);
  }
}

Measured memory_bytes: 128
#include<stdio.h>
long long int a[100001],d[100001],x[1001],syutu[1001],f[100001];
int main(void)
{
	long long int i,j,n,t,q,M,flg,a1,aba,cnt;
	M=9223372036854775807;
	scanf("%lld %lld %lld",&n,&t,&q);
	for(i=0;i<=n;i++) f[i]=M;
	for(i=1;i<=n;i++) scanf("%lld %lld",&a[i],&d[i]);
	for(i=1;i<=q;i++) scanf("%lld",&x[i]);
	flg=0; cnt=0;
	for(i=1;i<=n;i++){
		if(d[i]==1){
			a1=a[i];
			aba=i;
			flg=1;
		}
		if(d[i]==2&&flg==1){
			f[i]=(a1+a[i])/2;
			f[aba]=(a1+a[i])/2;
			flg=0;
		}
	}
	for(i=1;i<=q;i++){
		flg=0;
		if(d[x[i]]==1){
			for(j=x[i]+1;j<=n;j++){
				if(f[j]!=M&&f[j]>a[x[i]]+t) break;
				if(f[j]!=M&&f[j]<=a[x[i]]+t){	
					syutu[i]=f[j];
					flg=1;
					break;
				}
			}
			if(flg!=1) syutu[i]=a[x[i]]+t;
		}
		if(d[x[i]]==2){
			for(j=x[i]-1;j>=0;j--){
				if(f[j]!=M&&f[j]<a[x[i]]-t) break;
				if(f[j]!=M&&f[j]>=a[x[i]]-t){
					syutu[i]=f[j];
					flg=1;
					break;
				}
			}
			if(flg!=1) syutu[i]=a[x[i]]-t;
		}
	}
	for(i=1;i<=q;i++) printf("%lld\n",syutu[i]);
	return 0;
}

Measured memory_bytes: 2956
use std::io;
use std::str::FromStr;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn input_vec() -> Vec<i32> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn count(times: &Vec<i32>, f_vec: &Vec<i32>) -> i32 {
    let mut count = 0;
    for i in 0..times.len() {
        if times[i] == 1 && f_vec[i] == 1 {
            count += 1;
        }
    }
    count    
}

fn main() {
    let n: usize = input();
    let mut f: Vec<Vec<i32>> = Vec::new();
    for _ in 0..n {
        let f_vec = input_vec();
        f.push(f_vec);
    }
    let mut p: Vec<Vec<i32>> = Vec::new();
    for _ in 0..n {
        let p_vec = input_vec();
        p.push(p_vec);
    }

    let mut max = std::i32::MIN;
    for bit in 0..1<<10 {        
        let mut times = vec![0i32; 10];
        for i in 0..10 {
            if bit & (1<<i) != 0 {
                times[i] = 1;
            } else  {
                times[i] = 0;
            }
        }

        let mut flag = true;
        for t in &times {
            if *t == 1 {
                flag = false;
            }
        }
        if flag {
            continue;
        }

        let mut sum = 0;
        for i in 0..f.len() {
            sum += p[i][count(&times, &f[i]) as usize];
        }

        if sum > max {
            max = sum;
        }
    }
    println!("{}", max);
}


Measured memory_bytes: 4352
#!/usr/bin python3
# -*- coding: utf-8 -*-

x, k, d = map(int, input().split())
x = abs(x)

if x - k * d >= 0:
    print(x-k*d)
    exit()
else:
    k -= x//d
    x %= d
    if k%2==0:
        print(x)
    else:
        print(abs(x-d))


Measured memory_bytes: 9052
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

n,k = imap()
p = sorted(iarr())

ans = 0
for i in range(k): ans += p[i]
print(ans)


Measured memory_bytes: 37620
#include <iostream>
#include <string>

using namespace std;

char h[] = {'M','A','R','C','H'};
int n,s[5] = {0};

int main(void) {
    cin >> n;
    string buf;
    for(int i = 0;i < n;i++) {
        cin >> buf;
        for(int ii = 0;ii < 5;ii++) {
            if(buf[0] == h[ii])
                s[ii]++;
        }
    }
    unsigned long long int count = 0;
    for(int a = 0;a < 3;a++) {
        for(int b = a + 1;b < 4;b++) {
            for(int c = b + 1;c < 5;c++) {
                count =  count + (s[a] * s[b] * s[c]);
            }
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

ll a[1001]={},b[1001]={},c[1001]={};
ll d[1000001]={},e[3000001]={};

int main() {

	ll x,y,z,k;
	cin>>x>>y>>z>>k;
	rep(i,x){
		cin>>a[i];
	}
	ll r=0,f=0;
	rep(j,y){
		cin>>b[j];
		rep(i,x){
			d[r]=b[j]+a[i];
			r++;
		}
	}
	sort(d, d + r, greater<ll>());
	rep(l,z){
		cin>>c[l];
		rep(i,min(r,k)){
			e[f]=d[i]+c[l];
			f++;
		}
	}
	sort(e, e + f , greater<ll>());
	rep(i,k){
		cout<<e[i]<<endl;
	}

	return 0;

}


Measured memory_bytes: 31488
#include <stdio.h>

int main(void) {
    int n;

    scanf("%d", &n);

    if (n <= 111)
        printf("111\n");
    else if (n <= 222)
        printf("222\n");
    else if (n <= 333)
        printf("333\n");
    else if (n <= 444)
        printf("444\n");
    else if (n <= 555)
        printf("555\n");
    else if (n <= 666)
        printf("666\n");
    else if (n <= 777)
        printf("777\n");
    else if (n <= 888)
        printf("888\n");
    else
        printf("999\n");

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {
  
  int R,G,B,N;
  cin >> R >> G >> B >> N;

  int ans = 0;
  for(int i = 0;R*i <= N;i++) {
    for(int j = 0;j*G <= N-R*i;j++) {
      int b = N - R*i - G*j;
      if(b % B == 0) ans++;
    }
  }

  cout << ans << endl;
}



Measured memory_bytes: 256
N, K, Q = map(int, input().split())
s = []
[s.append(K-Q) for _ in range(N)]
for _ in range(Q):
  n = int(input())
  s[n-1] += 1
for t in s:
  if t > 0:
    print('Yes')
  else:
    print('No')

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

typedef pair<int,int> pii;
int N;
int A[100010];
vector<pii> V;

int main()
{
    scanf("%d",&N);
    for(int i = 0; i < N; i++)scanf("%d",A + i);
    if(N == 1)
    {
        if(A[0] % 2)printf("Second\n");
        else printf("First\n");
        return 0;
    }

    sort(A,A + N);
    reverse(A,A + N);
    for(int i = 0; i < N; i++)
    {
        if(i == N - 1 || (A[i] != A[i + 1]))
        V.push_back(make_pair(i + 1,A[i]));
    }

    if(V.size() == 1)
    {
        if((abs(V[0].second - N)) % 2 == 0)printf("Second\n");
        else printf("First\n");
        return 0;
    }

    int l = 0;
    while(l != V.size() - 1 && V[l].first <= V[l].second)l++;

    int res = 0;
    int a = V[l - 1].first,b = V[l].second;
    if(a == b)
    {
        if((V[l - 1].second - a) % 2)res = 1;
        if((V[l].first - a) % 2)res = 1;
        if(res == 1)printf("First\n");
        else printf("Second\n");
    }
    if(a > b)// l - 1とくっつく
    {
        if((V[l - 1].second - V[l - 1].first) % 2)printf("First\n");
        else printf("Second\n");
    }
    if(a < b)
    {
        if((V[l].first - V[l].second) % 2)printf("First\n");
        else printf("Second\n");
    }
    return 0;
}


Measured memory_bytes: 1784
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()) {
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t) {
	stringstream ss;
	ss << f;
	ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x)
#define debug(x)
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

//逆元 y=MOD-2 (MODは素数) O(log y)
ll powmod(ll x, ll y) {
	ll a = 1;
	while(y) {
		if(y & 1) a = a * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return a;
}

ll f[200010];
ll invf[200010];

ll comb(ll a, ll b) {
	// cout<<a<<" "<<b<<endl;
	ll ret = f[a] * invf[b] % MOD * invf[a - b] % MOD;
	return ret;
}


void mainmain() {
	int h, w;
	cin >> h >> w;
	int a, b;
	cin >> a >> b;
	f[0] = 1;
	invf[0] = 1;
	reep(i, 1, 200010) {
		f[i] = f[i - 1] * i % MOD;
		invf[i] = powmod(f[i], MOD - 2);
	}
	if(b+1==w){
		cout<<comb(h-a+b+1-2,h-a-1)<<endl;
		return;
	}
	ll ans = comb(h + w - 2, w - 1);
	// cout << ans << endl;
	rep(i, a) {
		int y = h - i;
		int x = b + 1;
		int c = i + 1;
		int d = w - b;
		ans -= comb(y + x - 2, x - 1) * comb(c + (d-1) - 2, c-1) % MOD;
		ans = (ans + MOD) % MOD;
		ans += comb(h-a + b+1 - 2, h-a-1) * comb(c + (d-1) - 2, c-1) % MOD;
		ans = (ans + MOD) % MOD;
	}
	cout << ans << endl;
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);
	mainmain();
}

Measured memory_bytes: 3328
use std::io::*;
use std::cmp;

fn read<T: std::str::FromStr>() -> T {
    let stdin = stdin();
    let mut buf = String::new();
	stdin.lock().read_line(&mut buf);
	buf.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
	read::<String>().trim().split_whitespace()
        .map(|w| w.parse().ok().unwrap()).collect()
}

fn main() {
    let v = read_vec::<usize>();
    let w = read_vec::<i64>();
    let ans = if v[0] == 1 {
        (v[2] as i64 - w[v[0]-1]).abs()
    } else {
        cmp::max((v[2] as i64 - w[v[0]-1]).abs(), (w[v[0]-2]-w[v[0]-1]).abs())
    };
    println!("{}",ans);
}


Measured memory_bytes: 4352
def main():
    s = input()
    arr = [0]*(len(s)+1)
    for i in range(len(s)):
        c = s[i]
        if c == "<":
            arr[i+1] = arr[i]+1
    for i in reversed(range(len(s))):
        c = s[i]
        if c == ">":
            arr[i] = max(arr[i], arr[i+1]+1)
    print(sum(arr))

if __name__ == "__main__":
    main()


Measured memory_bytes: 29124
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)

using namespace std;

const int N=2e5+100;
int n,x,y;

struct Tree{
	int n,cnt,head[N],clk,dep[N],in[N],out[N],lg[N<<1],q[N<<1],st[N<<1][22];
	struct edge{int to,nxt;}e[N<<1];
	void adde(int x,int y){
		e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt;
	}
	void dfs(int u,int par){
		in[u]=++clk; q[clk]=u;
		for (int i=head[u],v;i;i=e[i].nxt)
			if (v=e[i].to,v!=par)
				dep[v]=dep[u]+1,dfs(v,u),q[++clk]=u;
		out[u]=clk;
	}
	inline bool isanc(int x,int y){return in[x]<=in[y]&&out[y]<=out[x];}
	inline int Min(int x,int y){return dep[x]<dep[y]?x:y;}
	void st_init(){
		rep (i,1,clk) st[i][0]=q[i],lg[i]=i==1?0:lg[i>>1]+1;
		rep (j,1,20)
			for (int i=1;i+(1<<j-1)<=clk;i++)
				st[i][j]=Min(st[i][j-1],st[i+(1<<j-1)][j-1]);
	}
	void init(int _n){
		n=_n; cnt=clk=0; memset(head,0,n+1<<2);
		rep (i,1,n-1){
			int x,y; scanf("%d%d",&x,&y);
			adde(x,y); adde(y,x);
		}
		dfs(1,0),st_init();
	}
	inline int lca(int x,int y){
		if (in[x]>in[y]) swap(x,y);
		if (isanc(x,y)) return x;
		x=out[x],y=in[y]; int t=lg[y-x+1];
		return Min(st[x][t],st[y-(1<<t)+1][t]);
	}
	inline int dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
}T1,T2;

bool vis[N];

void bfs(int s){ //bfs出x能先到达的点
	queue<int> q; q.push(s),vis[s]=1; int ans=0;
	while (!q.empty()){
		int u=q.front(); q.pop();
		ans=max(ans,T2.dis(u,y));
		for (int i=T1.head[u],v;i;i=T1.e[i].nxt){
			v=T1.e[i].to;
			if (T2.dis(u,v)>2){puts("-1"); exit(0);}
			if (!vis[v]&&T1.dis(x,v)<T2.dis(y,v))
				vis[v]=1,q.push(v);
		}
	}
	printf("%d\n",ans<<1);
}

int main(){
	scanf("%d%d%d",&n,&x,&y);
	T1.init(n),T2.init(n);
	bfs(x);
	return 0;
}

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

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int n; cin >> n;
	int a[n]; rep(i,n) cin >> a[i];
	int b[n]; rep(i,n) cin >> b[i];
	int c[n-1]; rep(i,n-1) cin >> c[i];
	int ans = 0;
	rep(i,n) {
		ans += b[a[i] - 1];
		if(i > 0) {
			if(a[i-1] + 1 == a[i]) {
				ans += c[a[i-1]-1];
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp> 
//using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define f0(i,a,b) for(int i=a;i<b;i++)
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define f2(i,a,b) for(int i=a;i>b;i--)
#define f3(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define int long long
#define fi first
#define se second
#define ncr(n,r) fact[n]*modInv(fact[r])*modInv(fact[n-r])
#define modInv(a) binExp(a,mod-2)
#define mod 1000000007
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//#define os_find(k) find_by_order(k)
//#define os_order(k) order_of_key(k)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define make_graph(k) int x,y; f0(i,0,k){cin>>x>>y; adj[x].pb(y); adj[y].pb(x);}
#define test int t;cin>>t;while(t--)

int dp[101][100001];

signed main()
{
    fast

    int n,tw;
    cin>>n>>tw;

    int w[n+1], v[n+1];
    f1(i,1,n) cin>>w[i]>>v[i];

    f1(i,0,n) dp[0][i] = 0;
    f1(i,1,n)
    {
        f0(j,0,w[i]) dp[i][j] = dp[i-1][j];
        f1(j,w[i],tw)
        {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
    cout<<dp[n][tw];
}

Measured memory_bytes: 81704
#include<bits/stdc++.h> 
using namespace std; 
#define deb(x) cout <<"\n"<< (#x) << " = " << (x) << "\n"
const long long  INF = 1e18;
const long long mod=1e9+7 ;
void inputoutput()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0); 
   #ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
   #endif
       
}


vector<int> adj[100500];
vector<bool> vis(100500);
vector<int> d(100500);
queue<int> q ;



void bfs(int v)
{
   q.push(v);
   vis[v]=true;
   while(!q.empty())
   {
      int x=q.front();
      q.pop();
      for(auto u : adj[x])
      {
         if(!vis[u])
         {
            vis[u]=true;
            q.push(u);
            d[u] = d[v] + 1;
         }
      }
   }
}
void dfs(int v)
{
   vis[v]=true;
   for(auto u : adj[v])
   {
      if(!vis[u])
         dfs(u);
   }
}

void solve()
{
	int n;
	cin>>n;
	while(n--)
		cout<<"ACL";

}

int main()
{ 
   inputoutput() ;

   solve();
   


   return 0;
}


Measured memory_bytes: 5948
#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
    int N;
    long long t=1,a,c=0;
    scanf("%d",&N);
    while (N-->0){
        scanf("%lld",&a);
        if(a){
            if (t>1000000000000000000/a) c=1;
            else t*=a;
        }
        else{
            puts("0");
            return 0;
        }
    }
    if(c) puts("-1");
    else printf("%lld",t);
    return 0;
}

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

using namespace std;

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() {
  const int INF = 1e9 + 10;

  int N, M, L;
  cin >> N >> M >> L;
  vector<vector<int>> D(N, vector<int>(N, INF));
  for (int i = 0; i < N; i++) {
    D[i][i] = 0;
  }
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    D[a][b] = c;
    D[b][a] = c;
  }

  int Q;
  cin >> Q;
  vector<int> S(Q), T(Q);
  for (int i = 0; i < Q; i++) {
    cin >> S[i] >> T[i];
    S[i]--;
    T[i]--;
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        chmin(D[j][k], D[j][i] + D[i][k]);
      }
    }
  }

  vector<vector<int>> D2(N, vector<int>(N, INF));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (D[i][j] <= L) {
        D2[i][j] = 1;
      }
    }
    D2[i][i] = 0;
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        chmin(D2[j][k], D2[j][i] + D2[i][k]);
      }
    }
  }

  for (int i = 0; i < Q; i++) {
    if (D2[S[i]][T[i]] == INF) {
      cout << -1 << endl;
    } else {
      cout << D2[S[i]][T[i]] - 1 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 1920
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        Reader r = new Reader();   
        int N = r.i();
        println(180*(N-2));
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class Reader extends BufferedReader{
        Reader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}

Measured memory_bytes: 21204
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int D;
	scanf("%d", &D);
	int c[26], s[D][26], t[D], last[26];
	for (int i = 0; i < 26; ++i) scanf("%d", &c[i]);
	for (int i = 0; i < D; ++i) {
		for (int j = 0; j < 26; ++j) scanf("%d", &s[i][j]);
	}
	for (int i = 0; i < D; ++i) scanf("%d", &t[i]);
	fill_n(last, 26, -1);
	int ans = 0;
	for (int i = 0; i < D; ++i) {
		last[t[i] - 1] = i;
		ans += s[i][t[i] - 1];
		for (int j = 0; j < 26; ++j) ans -= c[j] * (i - last[j]);
		printf("%d\n", ans);
	}
	return 0;
}

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

using namespace std;

int main() {
    if (fopen("A.inp", "r"))
    freopen("A.inp", "r", stdin),
    freopen("A.out", "w", stdout);
    string str; cin >> str;
    cout << (str == "ABC" ? "ARC" : "ABC");
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <map>
using namespace std;
typedef long long lint;

int main() {
    int k, n;
    cin>>k>>n;
    vector<int> a(n+1);
    for(int i=0; i<n; ++i) {
        cin>>a[i];
    }
    a[n]=a[0]+k;
    
    vector<int> b(n);
    for(int i=0; i<n; ++i) {
        b[i]=a[i+1]-a[i];
    }

    int ans=0, start=0;
    for(int i=0; i<n; ++i) {
        ans+=b[i];
        start=max(b[i],start);
    }
    cout<<ans-start<<endl;
    

    return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <map>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
using namespace std;
int mod = 1e9 + 7;

int main()
{
	int N;
	cin >> N;
	vector<pair<int, int>> ord(N);
	rep(i, N)
	{
		int tmp;
		cin >> tmp;
		ord[i].second = i;
		ord[i].first = tmp;
	}
	sort(ALL(ord));
	rep(i,N)
	{
		cs(ord[i].second + 1);
	}
	return 0;
}

Measured memory_bytes: 1536
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all(C) std::begin(C), std::end(C)

int32_t H,W,h,w;
int64_t map[500][500];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> H>>W>>h>>w;
	for (int32_t i = 0; i < H; i+=h)
		for (int32_t j = 0; j < W; j += w)
	{
		map[i][j] = 1000000000 - 1;
	}
	for (int32_t i = h-1; i < H; i+=h)
		for (int32_t j = w-1; j < W; j += w)
	{
		map[i][j] = -1000000000;
	}

	int64_t sum = 0;
	for (int32_t i = 0; i < H; ++i)
		for (int32_t j = 0; j < W; ++j)
	{
		sum += map[i][j];
	}
	if (sum > 0) {
		out << "Yes\n";
		for (int32_t i = 0; i < H; ++i)
		{
			for (int32_t j = 0; j < W; ++j)
			{
				out << map[i][j] << ' ';
			}
			out << '\n';
		}
	}
	else {
		out << "No\n";
	}
	return 0;
}
#endif


Measured memory_bytes: 4864
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)*}
    };
}

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)*}
    };
}

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, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main(){

    input!{
        s: chars,
    }

    let ss: String = s.into_iter().collect();
    
    match &*ss{
        "SUN" => println!("7"),
        "MON" => println!("6"),
        "TUE" => println!("5"),
        "WED" => println!("4"),
        "THU" => println!("3"),
        "FRI" => println!("2"),
        "SAT" => println!("1"),
        _ => println!("something else"),
    }
}

Measured memory_bytes: 4352
x,y,a,b,c =map(int,input().split())
p = sorted(list(map(int,input().split())))[::-1]
q = sorted(list(map(int,input().split())))[::-1]
r = (list(map(int,input().split())))

p1 = p[:x]
q1 = q[:y]
l = sum(sorted(p1+q1+r)[::-1][:x+y])
print(l)


Measured memory_bytes: 29288
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
#include <map>
#include <cstring>
#include <utility>
#include <vector>
#include <cmath>

using namespace std;

typedef pair<int,int> P;
typedef long long int ll;


int main(){

  ios_base::sync_with_stdio(false);

  int N = 0;
  ll power = 1;
  ll m = pow(10,9)+7;
  cin>>N;
  for(int i=1;i<=N;i++){
    power = (power*i) % m;
  }
  cout<<power<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
ll mypow(ll x, ll n, ll m) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return mypow(x*x%m, n / 2, m);
	}
	else {
		return x * mypow(x, n - 1, m) % m;
	}
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll 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] % INF) % INF;
}
///////////////////////////////////////


int main() {
	int A, B, M; cin >> A >> B >> M;
	int a[100100], b[100100];
	int am = INF;
	int bm = INF;
	REP(i, A) {
		cin >> a[i];
		am = min(am, a[i]);
	}
	REP(i, B) {
		cin >> b[i];
		bm = min(bm, b[i]);
	}

	int ans = am + bm;
	REP(i, M) {
		int x, y, c;
		cin >> x >> y >> c;
		x--, y--;
		ans = min(ans, a[x] + b[y] - c);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
template<typename T = int, T mod = 1'000'000'007, typename U = long long>
struct umod{
    T val;
    umod(): val(0){}
    umod(U x){ x %= mod; if(x < 0) x += mod; val = x;}
    umod& operator += (umod oth){ val += oth.val; if(val >= mod) val -= mod; return *this; }
    umod& operator -= (umod oth){ val -= oth.val; if(val < 0) val += mod; return *this; }
    umod& operator *= (umod oth){ val = ((U)val) * oth.val % mod; return *this; }
    umod& operator /= (umod oth){ return *this *= oth.inverse(); }
    umod& operator ^= (U oth){ return *this = pwr(*this, oth); }
    umod operator + (umod oth) const { return umod(*this) += oth; }
    umod operator - (umod oth) const { return umod(*this) -= oth; }
    umod operator * (umod oth) const { return umod(*this) *= oth; }
    umod operator / (umod oth) const { return umod(*this) /= oth; }
    umod operator ^ (long long oth) const { return umod(*this) ^= oth; }
    bool operator < (umod oth) const { return val < oth.val; }
    bool operator > (umod oth) const { return val > oth.val; }
    bool operator <= (umod oth) const { return val <= oth.val; }
    bool operator >= (umod oth) const { return val >= oth.val; }
    bool operator == (umod oth) const { return val == oth.val; }
    bool operator != (umod oth) const { return val != oth.val; }
    umod pwr(umod a, U b) const { umod r = 1; for(; b; a *= a, b >>= 1) if(b&1) r *= a; return r; }
    umod inverse() const {
        U a = val, b = mod, u = 1, v = 0;
        while(b){
            U t = a/b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if(u < 0)
            u += mod;
        return u;
    }
};
using U = umod<>;
template<typename U>
struct NCR {
    vector<U> fact, ifact;
    NCR(int size){
        fact.resize(size + 1); ifact.resize(size + 1);
        fact[0] = 1;
        for(int i = 1; i <= size; i++) fact[i] = fact[i - 1] * i;
        ifact[size] = fact[size].inverse();
        for(int i = size - 1; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1);
    }
    U ncr(int n, int r){
        if(n < r) return 0;
        return fact[n] * ifact[r] * ifact[n - r];
    }
};
using N = NCR<U>;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k; cin >> n >> k;
	N kit(n);
	vector<U> dp(n + 1, 0);
	dp[0] = 1;
	for(int i = 0; i < k; i++){
		vector<U> ndp(n + 1, 0);
		int x; cin >> x;
		for(int j = 0; j <= n; j++){
			for(int c = 0; c <= x && c + j <= n; c++){
				ndp[j + c] += dp[j] * kit.ncr(n - j, c) * kit.ncr(n - c, x - c);
			}
		}
		dp = ndp;
	}
	cout << dp[n].val << '\n';
	return 0;
}


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

int main(){
    ll x, k, d;
    cin >> x >> k >> d;
    if(x < 0) x *= -1;

    ll q = x/d;
    ll r = x%d;

    ll ans;
    if(k>=q){
        if(k%2 == q%2) ans = r;
        else ans = d-r;
    }
    else ans = x - k*d;

    cout << ans << endl; 
}


Measured memory_bytes: 3544
H, W = list(map(int, input().split()))
field = []
for i in range(H):
    field.append(list(input()))

for y in range(H):
    for x in range(W):
        if field[y][x] == '.':
            count = 0
            if y - 1 >= 0:
                if x - 1 >= 0 and field[y-1][x-1] == '#':
                    count += 1
                if field[y-1][x] == '#':
                    count += 1
                if x + 1 < W and field[y-1][x+1] == '#':
                    count += 1

            if y + 1 < H:
                if x - 1 >= 0 and field[y+1][x-1] == '#':
                    count += 1
                if field[y+1][x] == '#':
                    count += 1
                if x + 1 < W and field[y+1][x+1] == '#':
                    count += 1

            if x - 1 >= 0 and field[y][x-1] == '#':
                count += 1
            if x + 1 < W and field[y][x+1] == '#':
                count += 1

            field[y][x] = count

for i in range(H):
    for j in range(W):
        print(field[i][j], end="")
    print("")


Measured memory_bytes: 3572
X = input()
"""
Tの前にSがどれだけあるか？
TSSTTTSS
"""
s_cnt = 0
t_cnt = 0
cnt = 0
for s in X:
    if s == "S":
        s_cnt += 1
    if s == "T":
        t_cnt += 1
        if t_cnt <= s_cnt:
            cnt += 2
        else:
            s_cnt = 0
            t_cnt = 0


print(len(X) - cnt)


Measured memory_bytes: 3500
#include <bits/stdc++.h>
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
#define all(x) (x).begin(), (x).end()
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
using namespace std;
 
int main()
{
	int F; cin >> F;
	int i = 1, p = 0;
	if(F == 1) cout << 1 << endl;
	else
	{
	 	while(p + 2 * i + 1 < F) p = p + i, i ++;
	 	if(p + 2 * i + 1 == F) cout << i + 1 << endl;
	 	else cout << i + 1 << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <bits/stdc++.h>
#include<utility>
#include<algorithm>
#define int long long int
int mod=1e9+7;
#define p_b push_back
#define p_f push_front
#define P_f pop_front
#define P_b pop_back
#define m_p make_pair
#define m_t make_tuple
#define len() length()
#define sz() size()
#define u_b upper_bound
#define l_b lower_bound
#define ins insert
#define str string 
#define bitcount __builtin_popcount
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define ld long double
#define db double
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define F first
#define S second
#define T third
#define endl "\n"
#define done return 0;
#define Fill(a,n,x) fill(a,a+n,x);
// #define fill(a,val) memset(a,val,sizeof(a))
using namespace std;
typedef map<int,int> Map;
typedef pair<int,int> pr;
typedef vector<int> vec;
const int INF = 1e18;
const int MAX =1e18;
int power(int a,int b)
{   
    if(b==0)
    return 1;
    int num=1;
    int m=mod;
    while(b!=1)
    { 
        if(b%2==0)
        { 
            a*=a;
            a%=m;
            b/=2;
        }
        else
        { 
            num*=a;
            num%=m;
            b--;
        }
        
    }
    return (a*num)%m;
}
void solve()
{
   str s;
   cin>>s;
   cout<<s.substr(0,3)<<endl;
}
int32_t main()
{
    int t;
    t=1;
    // cin>>t;
    while(t--)
    {   
        solve();
    }
    done;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define INF INT_MAX;
typedef long long ll;
using namespace std;

int64_t dfs(int64_t H){
  if(H==1) return 1;
  return 2*dfs(H/2)+1;
}

int main(){
  int64_t H; cin >> H;
  cout << dfs(H) << endl;
}


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

using namespace std;
using LL = long long;
using P = pair<int, int>;
using Tapris = tuple<int, int, int>;

#define REP(i, n) for(LL i = 0; i < n; ++i)
#define FOR(i, a, n) for(LL i = a; i < n; ++i)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

/*************** using variables ***************/
int n;
vector<LL> a, ruiseki;
/**********************************************/

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

    cin >> n;
    a.assign(n, 0);
    ruiseki.assign(n+1, 0);
    REP(i, n) cin >> a[i];
    
    FOR(i, 1, n+1){
        ruiseki[i] = ruiseki[i-1] + a[i-1];
    }

    map<LL, int> mp;

    int ans = 0;
    REP(i, n+1){
        if(mp.count(ruiseki[i])) ans += mp[ruiseki[i]];
        mp[ruiseki[i]]++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 15872
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define FOR(i,k,n) for((i)=(k);(i)<(n);(i)++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define pb push_back
#define all(a) (a).begin(),(a).end()  //greater<int>()
using namespace std;

int main(){
	int A,B;

	cin>>A>>B;

	if(A==1) A=14;
	if(B==1) B=14;


	if(A>B){
		cout<<"Alice";
	}

	else if(B>A){
		cout<<"Bob";
	}

	else{
		cout<<"Draw";
	}

   	return 0;
}


Measured memory_bytes: 256