akhauriyash/Code-Regression huggingface dataset:
use std::cmp::min;

#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let (n, ma, mb) = scan!(usize, usize, usize);
    let vs = scan!(usize, usize, usize;n);

    let mut dp = vec![vec![vec![1 << 60; n * 10 + 1]; n * 10 + 1]; n + 1];

    dp[0][0][0] = 0;
    for (i, &(a, b, c)) in vs.iter().enumerate() {
        for j in 0..dp[i].len() {
            for k in 0..dp[i][j].len() {
                if j >= a && k >= b {
                    dp[i + 1][j][k] = min(dp[i][j][k], dp[i][j - a][k - b] + c)
                } else {
                    dp[i + 1][j][k] = dp[i][j][k]
                }
            }
        }
    }

    let mut ans = 1 << 60;
    for d in &dp[n] {
        for i in 1..d.len() {
            for j in 1..d.len() {
                if i * mb == j * ma {
                    ans = min(ans, dp[n][i][j])
                }
            }
        }
    }

    if ans != 1 << 60 {
        println!("{}", ans)
    } else {
        println!("-1")
    }
}


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

const int max_n = 200000;

struct student
{
  bool win;
  int id;
  int next;
  int prev;
};

int main()
{
  int n, m, q;
  int a[max_n];
  int query[1000];

  cin >> n >> m >> q;
  for (int i=0;i<m;i++) scanf("%d", &a[i]); //cin >> a[i];
  for (int i=0;i<q;i++) scanf("%d", &query[i]); //cin >> query[i];

  student students[max_n];

  for (int i=0;i<n;i++)
  {
    students[i].win = true;
    students[i].id = i;
    students[i].next = (i+1) % n;
    students[i].prev = (i-1+n) % n;
  }

  int baton = 0;
  for (int i=0;i<m;i++)
  {
    if (a[i] % 2)
      for (int k=0;k<a[i];k++) baton = students[baton].prev;
    else
      for (int k=0;k<a[i];k++) baton = students[baton].next;

    int pre = students[baton].prev;
    int nxt = students[baton].next;
    students[baton].win = false;
    students[pre].next = nxt;
    students[nxt].prev = pre;
    baton = nxt;
  }

  for (int i=0;i<q;i++)
  {
    if (students[query[i]].win) cout << 1 << endl;
    else cout << 0 << endl;
  }

  return 0;
}

Measured memory_bytes: 5152
#include<iostream>
#include<cmath>
using namespace std;
int main(void){
	int d,n;
	long long x;
	cin>>d>>n;
	if(n<100){
		x=pow(100,d)*n;
	}
	else{
		x=pow(100,d)*101;
	}
	cout<<x<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,n) for(int i=a;i<n;i++)
#define M 1000000007
ll power(ll x, ll y, ll p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {   if (y & 1)
        res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
bool is(string s)
{
	for(int i=0;i<s.size()/2;i++)
	{
		if(s[i]!=s[s.size()-i-1])
		{
			return 0;
		}
	}
	return 1;
}
double x=1e-6;
int main()
{
	IOS;
	long double n;
	cin>>n;
	long double x1=n/3.0;
	n=x1*x1*x1;
	std::cout << std::fixed;
	cout<<setprecision(12)<<n;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

struct mint {
  ll x;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
};

mint factorial(ll n) {
  mint answer = 1;
  while (n > 1) {
    answer *= n;
    n--;
  }
  return answer;
}

mint combination(ll n, ll r) {
  return factorial(n) / (factorial(r) * factorial(n - r));
}

mint permutation(ll n, ll r) { return factorial(n) / factorial(n - r); }

// setprecision(8) 桁数指定
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

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

template <typename T>
void remove(std::vector<T>& vector, unsigned int index) {
  vector.erase(vector.begin() + index);
}

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}
// for (auto p : prime_factor(n)) {
//	while (p.second--) {
//		cout << p.first << endl;
//	}
//}

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

bool compare_by_b(pair<ll, ll> a, pair<ll, ll> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

vector<ll> Eratosthenes(const ll N) {
  bool is_prime[1000000 + 1];
  vector<ll> P;
  for (ll i = 0; i <= N; i++) {
    is_prime[i] = true;
  }
  for (ll i = 2; i <= N; i++) {
    if (is_prime[i]) {
      for (ll j = 2 * i; j <= N; j += i) {
        is_prime[j] = false;
      }
      P.emplace_back(i);
    }
  }
  return P;
}

typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

int main() {
  string s, t, u;
  int a, b;
  cin >> s >> t >> a >> b >> u;
  if (s == u) {
    a--;
  } else {
    b--;
  }

  cout << a << " " << b << endl;

  return 0;
}

Measured memory_bytes: 256
import io
import sys



# 関数 solve は，もちろん，問題に応じて書き換える
def solve(a):
    list1 = sorted(a)
    ab = str(list1[2])+str(list1[1])
    return int(ab)+int(list1[0])

# ここから下は，入力・出力形式が同じであれば，変えなくて良い．
def readQuestion():

    line = sys.stdin.readline().rstrip()
    listabc = line.split(" ")
    return listabc

def main():
    n = readQuestion()
    answer = solve(n)
    print(answer)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	ll a, b, c, x, y; cin >> a >> b >> c >> x >> y;
	ll res = 1e18;
	rep(i, 2*max(x, y) + 1)
	{
		int A = max(0LL, x - i / 2), B = max(0LL, y - i / 2);
		chmin(res, c*i + a * A + b * B);
	}
	cout << res << endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(), (x).end()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end());
// map<int,int> mp;

int main() {
  int n;
  cin >> n;
  vector<int> A(n), Amax(n);
  REP(i, n) cin >> A[i];

  Amax = A;

  sort(all(Amax));

  for (int i = 0; i < n; i++) {
    if (Amax.at(n - 1) == A[i])
      cout << Amax.at(n - 2) << endl;
    else
      cout << Amax.at(n - 1) << endl;
  }
}

Measured memory_bytes: 3200
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const long long  INF = 1e15;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);	
}

int main()
{
	ios_init();
	int n;
	LL zw[2];
	while(cin >> n >> zw[0] >> zw[1]) {
		vector<LL> a(n);
		REP(i,n) cin >> a[i];
		using P = pair<LL,LL>;
		
		vector<vector<LL>> dp(2, vector<LL> (n+1, -INF));
		reverse(ALL(a));

		FOR(j, 1, n+1) REP(i,2) {
			LL x;
			if(j == n) {
				x = zw[!i];
			} else {
				x = a[j];
			}
			dp[i][j] = abs(x-a[0]);
			FOR(k, 1, j) {
				if(i) {
					chmin(dp[i][j], abs(dp[!i][k]));
				} else {
					chmax(dp[i][j], abs(dp[!i][k]));
				}
			}
		}
		REP(i, 2) dpite(ALL(dp[i]));
		cout << dp[0].back() << endl;
	}
	return 0;
}


Measured memory_bytes: 384
using System;

class Solver
{
    static Scanner cin;
    public Solver() {}
    public static int Main()
    {
        cin = new Scanner();
        new Solver().solve();
        return 0;
    }
 
    public void solve()
    {
        int n, k;
        n = cin.nextInt();
        k = cin.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = cin.nextInt();
        }
        Array.Sort(a);
        int lb = lowerBound(a, k);
        if (lb == 0) {
            Console.WriteLine(0);
            return;
        }
        
        Array.Resize(ref a, lb);
        int sumUnderK = 0;
        for (int i = 0; i < lb; ++i) {
            sumUnderK += a[i];
        }
        if (sumUnderK < k) {
            Console.WriteLine(lb);
            return;
        }
        
        Array.Reverse(a);
        int answerLowest = k;
        bool[] dp = new bool[k];
        for (int i = 0; i < k; ++i) {
            dp[i] = false;
        }
        dp[0] = true;
        int possibleMax = 0;
        for (int i = 0; i < lb; ++i) {
            if (k - a[i] <= possibleMax) {
              answerLowest = a[i];
            }
         
            for (int j = k - a[i] - 1; j >= 0; --j) {
                if (dp[j]) {
                    dp[j + a[i]] = true;
                    possibleMax = Math.Max(possibleMax, j + a[i]);
                }
            }
        }

        Array.Reverse(a);
        Console.WriteLine(lowerBound(a, answerLowest));
    }
    
    public int lowerBound(int[] a, int k) {
        int n = a.Length;
        if (a[0] >= k) {
            return 0;
        }
        int l = 0;
        int r = n;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (a[mid] < k) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return r;
    }
}

class Scanner
{
    string[] s;
    int i;
 
    char[] cs = new char[] { ' ' };
 
    public Scanner()
    {
        s = new string[0];
        i = 0;
    }
 
    public string next()
    {
        while (i >= s.Length)
        {
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
        }
        return s[i++];
    }
 
    public int nextInt()
    {
        return int.Parse(next());
    }
 
    public long nextLong()
    {
        return long.Parse(next());
    }
 
    public double nextDouble()
    {
        return double.Parse(next());
    }
}

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

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args) {
        long n = in.l();

        long ans = 0;
        if (n % 2 == 0) {
            n /= 2;
            while (n > 0) {
                n /= 5;
                ans += n;
            }
        }

        System.out.println(ans);
    }

    static long f(int n) {
        return n < 2 ? 1 : n * f(n - 2);
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = super.read(cbuf, 0, cbuf.length);
            } catch (IOException e) {
                e.printStackTrace();
            }
            head = 0;
        }
        return cbuf[head++];
    }

    int i() {
        int k = next() - '0';
        boolean minus = k == -3;
        int n = minus ? 0 : k;
        while (0 <= (k = next() - '0') && k <= 9) n = 10 * n + k;
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }

    long l() {
        int k = next() - '0';
        boolean minus = k == -3;
        long n = minus ? 0 : k;
        while (0 <= (k = next() - '0') && k <= 9) n = 10 * n + k;
        return minus ? -n : n;
    }

    char[] s(final int N) {
        char[] s = new char[N];
        for (int i = 0; i < N; i++) {
            s[i] = next();
        }
        next();
        return s;
    }

    public int read(char[] cbuf) {
        int i;
        char c;
        for (i = 0; (c = next()) != ' ' && c != '\n'; i++) cbuf[i] = c;
        return i;
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }
}


Measured memory_bytes: 32572
S = input()
tmp = 0
ans = 0
for s in S:
  if s == "A" or s == "C" or s == "G" or s == "T":
    tmp += 1
  else:
    if tmp > ans:
      ans = tmp
    tmp = 0
  if tmp > ans:
    ans = tmp
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}


int main() {
    ll n, m, v, p;
    cin >> n >> m >> v >> p;
    vector<ll> z(n);
    for (int i = 0; i < n; i++) {
        cin >> z.at(i);
    }
    sort(z.begin(), z.end());
    reverse(z.begin(), z.end());
    ll ok = 0;
    ll ng = n;
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        ll vote = 0;
        for (int i = 0; i < n; i++) {
            if (i < p-1) {
                vote += m;
                continue;
            }
            if (z.at(mid) >= z.at(i)) {
                vote += m;
                continue;
            }
            vote += m - (z.at(i) - z.at(mid));
        }
        if (vote >= v * m && z.at(mid) + m >= z.at(p - 1)) {
            ok = mid;
        }
        else ng = mid;
    }
    cout << ok + 1 << endl;
}

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

int main()
{
  int n;

  cin >> n;
  while (n != 0){
    stack<int> a, b;
    int s[10];
    bool judge = true, j = false;
    for (int i = 0; i < 10; i++){
      cin >> s[i];
    }
    a.push(s[0]);
    for (int i = 1; i < 10; i++){
      if (a.top() < s[i]){
        a.push(s[i]);
      }
      else if (!j){
        b.push(s[i]);
        j = true;
      }
      else if (b.top() < s[i]){
        b.push(s[i]);
      }
      else {
        judge = false;
        break;
      }
    }

    if (judge){
      cout << "YES\n";
    }
    else {
      cout << "NO\n";
    }
    n--;
  }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rep(i,n) REP(i,0,n)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

using namespace std;
typedef long long ll;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b)
        cout << c << endl;
    else if (a == c)
        cout << b << endl;
    else
        cout << a << endl;
    return 0;
}




Measured memory_bytes: 256
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
  
    public static void main(String[] args) 
    { 
        FastReader sc=new FastReader(); 
		int n=sc.nextInt();
		int[] a=new int[n];
		
		for(int i=0;i<n;i++) a[i]=sc.nextInt();
		long sum=0;
		for(int i=1;i<n;i++){
			if(a[i]<a[i-1]){
				sum+=a[i-1]-a[i];
				a[i]=a[i-1];
			}
		}
		System.out.println(sum);
	
    	
    }
}

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


int main();
bool prime_chk(int num);



int main(){
	
	int a[1000] = {0};
	int d[1000] = {0};
	int n[1000] = {0};
	int result[1000] = {0};
	int n_series;
	int s_series;
	int nth_prime_num;
	int i,i_dataset;
	
	bool prime_flg;
	
	
	//データ入力
	i_dataset = 0;
	while(1){
		scanf("%d %d %d", &a[i_dataset], &d[i_dataset], &n[i_dataset]);
		
		if( a[i_dataset] == 0 && d[i_dataset] == 0  && n[i_dataset] == 0) break; //0 0 0が入力されると処理終了
		else i_dataset++; //データ数を記録
	}
	
	
	//計算開始
	
	for (i=0;i<i_dataset;i++){
		
		nth_prime_num = 0;
		n_series = 1;
		
		while(1){
			if (n_series == 1) s_series = a[i];
			else s_series = a[i] + (n_series - 1) * d[i];
			
			prime_flg = prime_chk (s_series);
			if (prime_flg==true) nth_prime_num++;
			
			if (nth_prime_num == n[i]) {
				result[i] = s_series;
				break;
			}
			
			n_series++;
		}
	}
	
	for(i=0;i<i_dataset;i++){
		printf("%d\n",result[i]); //結果出力
	}
	
	return 0;
}

bool prime_chk(int num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrt_num = sqrt(num);
    for (int i = 3; i <= sqrt_num; i += 2){
        if (num % i == 0){
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}


Measured memory_bytes: 2588
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,X;
  cin >> N >> X;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  sort(A.begin(),A.end());
  int sum=0,count=0;
  for(int i=0;i<N;i++){
    sum+=A.at(i);
    count++;
    if(sum>X){
      count--;
      break;
    }
    else if(sum==X){
      break;
    }
  }
  if(sum<X){
    count--;
  }
  cout << count << endl;
}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

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

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int n;
    cin >> n;
    vi a(n), s;
    rep(i, n) cin >> a[i];
    vi m(n), rm(n);
    rep(i, n) {
        if (i == 0) m[i] = a[i];
        else m[i] = max(m[i-1], a[i]);
    }
    repr(i, n) {
        if (i == n-1) rm[i] = a[i];
        else rm[i] = max(rm[i+1], a[i]);
    }
    rep(i, n) {
        int l = (i!=0?m[i-1]:0);
        int r = (i!=n-1?rm[i+1]:0);
        cout << max(l, r) << endl;
    }
    return 0;
}


Measured memory_bytes: 3968
# coding: utf-8
# Here your code !
xyz = raw_input().split(" ")
c1, c2 = 0, 0
for i in xyz:
    if i == "5":
        c1 += 1
    elif i == "7":
        c2 += 1
if (c1 == 2 and c2 == 1):
    print "YES"
else:
    print "NO"

Measured memory_bytes: 6512
import collections
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
n=int(input())
s=list(list(input()) for i in range(n))
count=0
for i in range(n):
    s[i].sort()
s.sort()

for i in range(n):
    s[i]=''.join(map(str, s[i]))
    
c = collections.Counter(s)
d=c.most_common()

for i in range(len(d)):
    if d[i][1]>1:
        count+=combinations_count(d[i][1], 2)
    else:
        break
print(count)

Measured memory_bytes: 37064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int n; cin >> n;
    cout << n/3 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define tc() int t; cin>>t; while(t--)
#define print(n) cout<<n<<"\n"
#define inp(n) int n; cin>>n
#define all(cont) cont.begin(), cont.end()
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define maxn 1000010
#define f  first
#define s  second
#define fora(var, start, end) for(int var = start; var < end; var++)
int main()
{
    inp(n);
    string s;
    cin>>s;
    int sum=1;
    fora(i,1,n)
    {
       if(s[i]==s[i-1])continue;
       else
       {
        sum++;
       }


    }
    print(sum);



    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define bitsz(x) int(__builtin_popcount(x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
#define mod 1000000007
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int n;
vector<int> dist; //根からの距離のパリティ
vector<vector<P>> G;

void dfs(int v, int d) {
    dist[v] = d;
    for (auto u : G[v]) {
        if (dist[u.first] == -1) {
            dfs(u.first, (d+u.second)%2);
        }
    }
}

int main() {
    cin >> n;
    dist.resize(n); G.resize(n);
    rep(i,n) dist[i] = -1; //未訪問なら-1
    rep(i,n-1) {
        int a,b,c; cin >> a >> b >> c;
        a--; b--;
        c %= 2;
        G[a].push_back(P(b,c));
        G[b].push_back(P(a,c));
    }
    dfs(0,0);
    rep(i,n) cout << dist[i] << endl;
}

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

int main(){
    ll K, T;
    cin >> K >> T;
    map<ll, ll> mp;
    ll mx = 0, sum = 0;
    rep(i, 0, T){
        ll a;
        cin >> a;
        sum += a;
        mx = max(mx, a);
    }
    if(mx - (sum-mx) > 1){
        cout << mx - (sum - mx) -1 << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
H,W=map(int,input().split())
C=[list(map(int,input().split())) for i in range(10)]
A=[list(map(int,input().split())) for i in range(H)]

for k in range(10):
  for i in range(10):
    for j in range(10):
      C[i][j]=min(C[i][j],C[i][k]+C[k][j])
ans=0
for i in range(H):
  for j in A[i]:
    if j!=1 and j!=(-1):
      ans+=C[j][1]
print(ans)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;

int main() {
  string s;
  cin >> s;

  if (s == "AAA" || s == "BBB") {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
}


Measured memory_bytes: 256
D, G = map(int, input().split())
p = []
c = []
PC = [0] + [list(map(int, input().split())) for _ in range(D)]
 
def dfs(G, i):
    if i == 0:
        return 10**12
    n = min(G // (100 * i), PC[i][0])
    tmp = n*100*i
    if n == PC[i][0]:
        tmp += PC[i][1]
    if tmp < G:
        n += dfs(G-tmp, i-1)
    return min(n, dfs(G, i-1))
 
print(dfs(G, D))

Measured memory_bytes: 3064
n = int(input())
A = []
for i in range(n):
    A.append(input())
m = int(input())
B =[]
for j in range(m):
    B.append(input())

C = []

for i in list(set(A)):
    C.append(A.count(i) - B.count(i))
print(max(max(C), 0))

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

int main(){
	long long N;
	cin >> N;
	long long ans=0;
	for(long long i=1;i*i<=N;i++){
		if(N%i==0 && (N/i>i+1))ans+=N/i-1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(long i=0; i<(long)(n);i++)
#define REP(i,s,t) for(long i=s; i<t; i++)
#define RNG(i,s,t,u) for(long i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()
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; }


vector<int> par;

void Initpar(int n){
  par = vector<int>(n); 
  for(int i=0; i<n; i++) par.at(i) = i;
}

int root(int x){
  if(x == par.at(x)) return x;
  else return par.at(x) = root(par.at(x));
}

void unite(int x, int y){
  int rx = root(x);
  int ry = root(y);
  if(rx == ry) return ;
  if(rx < ry) par.at(ry) = rx;
  else par.at(rx) = ry;
}

bool same(int x, int y){
  return root(x) == root(y);
}

void update_par(){
  for(int i=0;i<par.size();i++){
    root(i);
  }
}

int main(){
  long n,m;
  cin >> n >> m;
  Initpar(n);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--;b--;
    unite(a,b);
  }
  update_par();
  set<int> st;
  rep(i,n){
    st.insert(par.at(i));
  }
  cout << st.size()-1 << endl;
}

Measured memory_bytes: 7660
#include <bits/stdc++.h>
constexpr int INF = 1001001001;
using ll = long long;
using namespace std;
int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> s(h+1, vector<char>(w+1));
    for (int i = 0; i < h; i++) {
        string si;
        cin >> si;
        for (int j = 0; j < w; j++)
            s[i][j] = si[j];
    }
    
    vector<vector<int>> t(h+1, vector<int>(w+1, INF));
    t[0][0] = (s[0][0] == '.' ? 0 : 1);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '.' && s[i+1][j] == '#')
                t[i+1][j] = min(t[i+1][j], t[i][j] + 1);
            else
                t[i+1][j] = min(t[i+1][j], t[i][j]);

            if (s[i][j] == '.' && s[i][j+1] == '#')
                t[i][j+1] = min(t[i][j+1], t[i][j] + 1);
            else
                t[i][j+1] = min(t[i][j+1], t[i][j]);

        }
    }
    
    cout << t[h-1][w-1] << endl;
    
    return 0;
}


Measured memory_bytes: 256
//##MohK..
//21/04/2020....6.13...
//Ya Rab....
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
int main(){
    ll x,y,z;
    cin>>x>>y>>z;
    cout<<z<<" "<<x<<" "<<y;

    return 0;
}


Measured memory_bytes: 256
from itertools import product

# 入力
N, M = map(int, input().split())
k, s = zip(
    *(
        (int(k), list(map(int, s.split())))
        for _ in range(M)
        for k, s in [input().split(maxsplit=1)]
    )
)
p = list(map(int, input().split()))

# 全探索で解を求める
ans = sum(
    all(
        sum(t[j - 1] for j in S) % 2 == P
        for S, P in zip(s, p)
    )
    for t in product(range(2), repeat=N)
)

# 出力
print(ans)


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

using namespace std;

int main() {
  string s, last3;

  cin >> s;

  while (s.size() >= 3)
  {
    last3 = s.substr(s.size() - 3, 3);
    s.pop_back();
    s.pop_back();
    s.pop_back();
    if (last3 == "eam")
    {
      if (s.substr(s.size() - 2, 2) == "dr")
      {
        s.pop_back();
        s.pop_back();
        continue;
      }
      else
      {
        cout << "NO" << endl;
        return 0;
      }
    }
    else if (last3 == "mer")
    {
      if (s.substr(s.size() - 4, 4) == "drea")
      {
        s.pop_back();
        s.pop_back();
        s.pop_back();
        s.pop_back();
        continue;
      }
      else
      {
        cout << "NO" << endl;
        return 0;
      }
    }
    if (last3 == "ase")
    {
      if (s.substr(s.size() - 2, 2) == "er")
      {
        s.pop_back();
        s.pop_back();
        continue;
      }
      else
      {
        cout << "NO" << endl;
        return 0;
      }
    }
    else if (last3 == "ser")
    {
      if (s.substr(s.size() - 3, 3) == "era")
      {
        s.pop_back();
        s.pop_back();
        s.pop_back();
        continue;
      }
      else
      {
        cout << "NO" << endl;
        return 0;
      }
    }
    else
    {
      cout << "NO" << endl;
      return 0;
    }
  }

  if (s.size() == 0)
  {
    cout << "YES";
  }
  else
  {
    cout << "NO";
  }

  return 0;
}


Measured memory_bytes: 512
N, M, X = map(int, input().split())
c_list = []
a_list = []
for i in range(N):
    tmp = list(map(int, input().split()))
    c_list.append(tmp.pop(0))
    a_list.append(tmp)

cost = 100000000000
flg = False
for cnt in range(2 ** N):
    cost_tmp = 0
    score_tmp = [0] * M
    cnt_str = format(cnt, 'b')
    cnt_str = cnt_str[::-1]
    
    for i in range(len(cnt_str)):
        if(cnt_str[i] == '1'):
            cost_tmp += c_list[i]
            for j in range(M):
                score_tmp[j] += a_list[i][j]
    if(sum(x >= X for x in score_tmp) == M):
        cost = min(cost, cost_tmp)
        flg = True

if(flg):
    print(cost)
else:
    print(-1)

Measured memory_bytes: 9248
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>
 
//#define int long long
 
#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
#define endl '\n'
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
mt19937 mrand(random_device{}());
 
double PI = acos((double)-1);
const ld eps = 1e-7;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
//const ll mod = 1e9 + 7;
const ll mod = 998244353;
	
void solve();
void scan();
 
signed main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cout << fixed; cout.precision(15);
	solve();
	return 0;
}

const int S = 7e3 + 1;

ll cnt[S];

void add(ll& a, ll b) {
	a += b;
	if (a >= mod)
		a -= mod;
}

void solve() {
	int n; cin >> n;
	ll ans = 0;
	ll s; cin >> s;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	fill(cnt, cnt + S, 0);
	for (int i = 0; i < n; i++) {
		add(cnt[0], 1);
		for (int j = s; j >= a[i]; j--) {
			if (j == s) add(ans, (n - i) * 1ll * cnt[j - a[i]] % mod);
			else add(cnt[j], cnt[j - a[i]]);
		}
	}
	cout << ans << endl;
    return;
}

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

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

    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A.at(i);
    }

    ll ans = 0;
    ll sum = 0;
    int right = 0;
    for (int left = 0; left < N; ++left) {
        while (right < N && (sum ^ A.at(right)) == (sum + A.at(right))) {
            sum += A.at(right++);
        }
        ans += right - left;
        if (left == right) {
            right++;
        } else {
            sum -= A.at(left);
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] locations = new int[n];
        for(int i = 0; i < n; i++)
            locations[i] = sc.nextInt();

        long minDist = Long.MAX_VALUE;
        for(int i = 0; i <= n - k; i++) {
            int left = locations[i];
            int right = locations[i + k - 1];
            minDist = Math.min(minDist,
                right - left + Math.min(Math.abs(left), Math.abs(right))
            );
        }
        System.out.println(minDist);
    }
}


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

int main(void){
    int n;
    cin >> n;
    
    int ans = 0;
    int l, r;
    int i;
    for(i = 1; i <= n; i++){
        cin >> l >> r;
        ans += r - l + 1;
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back


int main() {
    int n;
    while(cin>>n){
        if(n==-1)break;
        
        string ans="";
        while(n>0){
            ans+='0'+(n%4);
            n=n/4;
        }
        reverse(all(ans));
        if(ans=="")ans='0';
        cout<<ans<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
int main(){
	string S;  
	cin >> S; 
	int L = S.size();  
	int ans = 114514; 
	for(int i = 0; i < L - 2; i++){
		int a = 100 * (S.at(i) - '0') + 10 * (S.at(i+1) - '0') 
			+ (S.at(i+2) - '0');
		ans = min(ans, abs(a - 753)); 
	}
	cout << ans << endl; 
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
break_step = [INT() for _ in range(M)] + [0]

comb = [0]*(N + 1)
comb[0] = 1

index = 0
for i in range(1, N + 1):
	if break_step[index] == i:
		comb[i] = 0
		index += 1
	else:
		if i == 1:
			comb[i] = 1
		else:
			comb[i] = comb[i - 2] + comb[i - 1]

print(comb[N]%mod)

Measured memory_bytes: 478156
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;
// << fixed << setprecision
// --------------------------------------
int h, n;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> h >> n;
  vector<int> a(n);
  vector<int> b(n);

  REP(i, n) cin >> a[i] >> b[i];
  int dp[20005];

  REP(i, 20005) dp[i] = INF;
  dp[0] = 0;

  REP(i, n) {
    FOR(j, 1, h + 1) {
      dp[j] = min(dp[j], dp[max(0, j - a[i])] + b[i]);
    }
  }

  cout << dp[h] << endl;
}


Measured memory_bytes: 3736
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
	int a,b,c,x;
	cin>>a>>b>>c>>x;
	x/=50;
	int i,j,k,num=0;
	for(i=0;i<=a;i++)
	{
		for(j=0;j<=b;j++)
		{
			for(k=0;k<=c;k++)
			{
				if(10*i+2*j+1*k==x)
				{
					num++;
				}
			}
		}
	}
	cout<<num;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
class Main{
	public static void main(String args[]) throws Exception{
		Scanner sc = new Scanner(System.in);
    int a= sc.nextInt();
    int b= sc.nextInt();
    int c= sc.nextInt();
    int d= sc.nextInt();

    int max = a;
    int otherSum = b+c;

    if(max < b){
      max = b;
      otherSum = a+c;
    }

    if(max < c){
      max = c;
      otherSum = a+b;
    }

    for(int i=0; i<d; i++){
  		max = max*2;
  	}

    int sum = max + otherSum;
    System.out.println(sum);
	}
}

Measured memory_bytes: 20820
#include <iostream>
#include <string>
#include <regex>

int input_shuffle_num();
void shuffle(std::string& deck, int n);
void output(std::vector<std::string> ans);

int main()
{
	std::string deck;
	std::vector<std::string> ans;
	while (std::cin >> deck, deck != "-")
	{
		int n = input_shuffle_num();
		shuffle(deck, n);
		ans.emplace_back(deck);
	}
	output(ans);
}

int input_shuffle_num()
{
	int n;
	std::cin >> n;
	return n;
}

void shuffle(std::string& deck, int n)
{
	int h;
	for (int i = 0; i < n; i++)
	{
		std::cin >> h;
		std::string above_deck = deck.substr(0, h);
		std::string below_deck = deck.substr(h);
		deck = below_deck + above_deck;
	}
}

void output(std::vector<std::string> ans)
{	
	for (auto deck : ans)
	{
		std::cout << deck << std::endl;
	}
}






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

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

int N;
string S;
double V,R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>V>>S;
		if(S=="JPY") R+=V;
		else R+=V*380000;
	}
	_P("%.12lf\n",R);
}


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


Measured memory_bytes: 256
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long

int main(void)
{
  ll x, k, d, i;
  scanf("%lld %lld %lld", &x, &k, &d);

  ll abx = (x > 0) ? x : -x;
  ll div = abx / d;

  if (div > k)
    div = k;
  if (x < 0)
    x += div * d;
  else if (x > 0)
    x -= div * d;
  //0 or ギリギリ
  ll rest = k - div;

  if (rest & 1)
  {
    if (x <= 0)
      x += d;
    else if (x > 0)
      x -= d;
  }
  printf("%lld\n", (x > 0) ? x : -x);
  return 0;
}


Measured memory_bytes: 1720
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  while(1){
  int count=0;
  int N;
  cin>>N;
  if(N==0)
  break;
  if(N%1111==0){
    cout<<"NA"<<endl;
    continue;
  }
   int L,S;
  while(N!=6174){
    int n[4];

   n[0]=N/1000;
   n[1]=N/100%10;
   n[2]=N/10%10;
   n[3]=N%10;

  sort(n,n+4);
  L=1000*n[3]+100*n[2]+10*n[1]+n[0];
  S=1000*n[0]+100*n[1]+10*n[2]+n[3];
  N=L-S;
  count++;
 }
 cout<<count<<endl;
 }
 return 0;
}

Measured memory_bytes: 1180
class Node:
    def __init__(self):
        self.parent = -1
        self.sibling = -1


def dfs(v, d=0):
    G[v].depth, G[v].height = d, 0
    if G[v].left != -1:
        G[v].height = max(G[v].height, dfs(G[v].left, d+1) + 1)
    if G[v].right != -1:
        G[v].height = max(G[v].height, dfs(G[v].right, d+1) + 1)
    return G[v].height

N = int(input())
G = [Node() for _ in range(N)]
for _ in range(N):
    idx, *children = [int(x) for x in input().split()]
    G[idx].left, G[idx].right = children
    if G[idx].left != -1 and G[idx].right != -1:
        G[G[idx].left].sibling, G[G[idx].right].sibling = G[idx].right, G[idx].left
    if G[idx].left != -1 or G[idx].right != -1:
        G[idx].type = 'internal node'
    else:
        G[idx].type = 'leaf'
    for child in children:
        if child != -1:
            G[child].parent = idx
root = [i for i, x in enumerate(G) if x.parent == -1][0]
G[root].type = 'root'
dfs(root)
for i, node in enumerate(G):
    print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i, node.parent, node.sibling, (node.left != -1) + (node.right != -1), node.depth, node.height, node.type))

Measured memory_bytes: 7836