akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(2e5) + 5;
constexpr double EPS = 1e-9;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i > 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int main() {
    int n;
    cin >> n;
    vector<P> task;
    REP(i,n){
        ll a, b;
        cin >> a >> b;
        task.push_back({b, a});
    }
    SORTR(task);
    ll now = IINF;
    bool ok = true;
    REP(i,n){
        //cout << now << endl;
        now = min(now, task[i].first);
        now -= task[i].second;
    }
    cout << (now>=0?"Yes":"No") << endl;
    return 0;
}



Measured memory_bytes: 6384
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
 
#define int ll
 
typedef int64_t ll;
static const int MOD = 1000000007;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const int INF = 1000010000;
//int dx4[4] = {0,0,1,-1}, dy4[4] = {1,-1,0,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define NP next_permutation
#define PQ priority_queue
#define UB upper_bound
#define LB lower_bound
#define SZ(a) signed((a).size())
#define LEN(a) signed((a).length())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).begin(),(c).end());reverse((c).begin(),(c).end());
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REP1(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREP1(i,x) for(int i=((int)(x));i>0;i--)
#define ALL(x) (x).begin(),(x).end()
#define YESNO(x) puts((x)?"YES":"NO")
#define YesNo(x) puts((x)?"Yes":"No")

int dp[51][51][2501]={};

signed main(){
    int N,A;
    cin >> N >> A;
    vector<int> vec;
    REP(i,N){
        int tmp;
        cin >> tmp;
        vec.PB(tmp);
    }

    dp[0][0][0] = 1;
    REP1(i,SZ(vec)) REP(j,i+1) REP(k,2501){
        if(k<vec[i-1]) dp[i][j][k] += dp[i-1][j][k];
        else if(j>0) dp[i][j][k] += dp[i-1][j][k] + dp[i-1][j-1][k-vec[i-1]];
    }

    int ans = 0;
    REP1(i,N) ans += dp[N][i][i*A];
    cout << ans << endl;
}















Measured memory_bytes: 49024
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 16;
const int INF = 1e9;
int N;
int dp[1 << MAX_N];
int t[MAX_N][MAX_N + 1];

int main()
{
    while (cin >> N, N) {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j <= N; ++j)
                cin >> t[i][j];

        fill(dp, dp + (1 << N), INF);
        dp[0] = 0;

        for (int S = 0; S < (1 << N); ++S) {
            for (int u = 0; u < N; ++u) {
                if (!(S >> u & 1)) {
                    dp[S | 1 << u] = min(dp[S | 1 << u], dp[S] + t[u][0]);
                    for (int v = 0; v < N; ++v) {
                        if (S >> v & 1)
                            dp[S | 1 << u] = min(dp[S | 1 << u], dp[S] + t[u][v + 1]);
                    }
                }
            }
        }

        cout << dp[(1 << N) - 1] << endl;
    }

    return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector <long long> B(N-1);
    long long ans = 0;
    cin >> B.at(0);
    ans += B.at(0);
    for (int i=1; i<N-1; i++) {
        cin >> B.at(i);
        ans += min(B.at(i-1), B.at(i));
    }
    ans += B.at(N-2);
    cout << ans << endl;
}

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

int n, x;
int a[111];

int main(){
  ios_base::sync_with_stdio(false);
  
  int ans = 0;

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

  sort(a, a+n);
  
  while(ans < n && x >= a[ans]){
    x -= a[ans];
    ans++;
  }

  if(x && ans >= n){
    cout << n-1 << endl;
  } else {
    cout << ans << endl;
  }

  return 0;
}



Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.array, std.range, std.algorithm;

void main() {
    long r, d, x;
    readf("%d %d %d", &r, &d, &x);

    foreach (i; 0..10) {
        x = r*x - d;
        writeln(x);
    }

}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>

#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long int ll;

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

  vector<ll> a(n);
  rep(i, n) cin >> a.at(i);

  ll mins = 0;
  if ((n - 1) % (k - 1) == 0)
    mins = (n - 1) / (k - 1);
  else
    mins = (n - 1) / (k - 1) + 1;
  cout << mins << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int main() {
	fastio;
	int N, M;
	cin >> N >> M;

	int A[100], sum = 0;
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
		sum += A[i];
	}

	sort(A, A + N);

	double c = sum / 4.0 / M;
	if (A[N - M] >= c) cout << "Yes";
	else cout << "No";

	return 0;
}

Measured memory_bytes: 256
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！
    配列は少し多めにとっておく

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include<cstring>
//namespace
using namespace std;
//繰り返し
#define REP(i, m, n) for(int i=(int)m; i<(int)n; ++i)
#define rep(i, n) REP(i, 0, n)
//イテレータ
#define all_range(C) begin(C), end(C)
//簡略化
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
typedef pair<string,int> pst;

const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
//最大最小
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) {if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) {if(a<b) a=b;}

//関数

//最大公約数を求める
ll my_gcd(ll x, ll y) {
  ll r;

  while(y!=0) {
    r = x%y;
    x = y;
    y = r;
  }

  return x;
}

//最小公約数を求める
ll my_lcm(ll x, ll y) {

  return (x*y)/my_gcd(x,y);
}

//xのy乗を求める ※参考：10^18乗まで
ll my_pow(ll x, ll y) {
  ll sum = 1;

  while(y>0) {
    sum *= x;
    --y;
  }

  return sum;
}

/*考えを書くスペース


*/

//main.cpp----------------------------
#define MAX 1000

int main() {
  int n;
  int v[21], c[21];

  cin >> n;
  rep(i, n) cin >> v[i];
  rep(i, n) cin >> c[i];

  int cost = 0;
  rep(i, n) {
    if(v[i]>c[i]) {
      cost += v[i]-c[i];
    }
  }
  cout << cost << endl;
  return 0;
}


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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

const int mod = 1e9 + 7;
mt19937 rng( (int)chrono::steady_clock::now().time_since_epoch().count() );

struct Mint {
  int a;
  Mint(int _a = 0) : a(_a) {}
  friend ostream& operator << (ostream &out, const Mint &_) {
    out << _.a;
    return out;
  }

  bool operator == (const Mint &_) const { return a == _.a; }
  bool operator ! () const { return !a; }

  Mint operator + (const Mint &_) const {
    int ret = a + _.a;
    return ret < mod ? Mint(ret) : Mint(ret - mod);
  }
  Mint operator - (const Mint &_) const { return *this + Mint(mod - _.a); }
  Mint operator * (const Mint &_) const { return Mint( (int)( (LL)a * _.a % mod) ); }
  friend Mint& operator += (Mint &a, const Mint &b) { return a = a + b; }
  friend Mint& operator -= (Mint &a, const Mint &b) { return a = a - b; }
  friend Mint& operator *= (Mint &a, const Mint &b) { return a = a * b; }
  Mint& operator ++ () { return *this = *this + Mint(1); }
  Mint& operator -- () { return *this = *this - Mint(1); }

  template<class T> Mint binPow(T exp) const {
    Mint ret(1), c = *this;
    for (; exp; exp >>= 1, c *= c) if (exp & 1) ret *= c;
    return ret;
  }
};

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

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafClover

  int n, x; cin >> n >> x;
  vector<int> l(n);
  for (auto &i : l) cin >> i;
  sort(all(l) ); reverse(all(l) );

  vector<vector<vector<Mint> > > f(n + 1, vector<vector<Mint> >(n + 1, vector<Mint>(x + 1) ) );
  f[0][0][0] = Mint(1);
  for (int i = 0; i + 1 < sz(f); ++i) {
    for (int j = 0; j < sz(f[i]); ++j) {
      for (int k = 0; k < sz(f[i][j]); ++k) if (f[i][j][k].a) {
        if (k + l[i] <= x) f[i + 1][j + 1][ k + l[i] ] += f[i][j][k] * Mint(j + 1);

        f[i + 1][j][k] += f[i][j][k] * Mint(k - j * (l[i] - 1) );
        for (int bonus = 1; bonus < l[i] && k + bonus <= x; ++bonus) f[i + 1][j][k + bonus] += f[i][j][k] * Mint(2 * j);

        if (j) {
          for (int bonus = 0; bonus < l[i] - 1 && k + bonus <= x; ++bonus) f[i + 1][j - 1][k + bonus] += f[i][j][k] * Mint( (j - 1) * (l[i] - 1 - bonus) );
        }
      }
    }
  }

  Mint ans;
  for (int j = 0; j < sz(f.back() ); ++j) ans += f.back()[j][x];

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 20864
#include <iostream>
using namespace std;
int decode(string s)
{
  int sum = 0, num = 1;
  for(int i=0; i<s.length(); i++){
    char c = s[i];
    switch(c){
    case 'm':
      sum += 1000 * num;
      num = 1;
      break;
    case 'c':
      sum += 100 * num;
      num = 1;
      break;
    case 'x':
      sum += 10 * num;
      num = 1;
      break;
    case 'i':
      sum += num;
      num = 1;
      break;
    default:
      num = c - '0';
    }
  }
  return sum;
}
int main()
{
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    string s1,s2;
    cin >> s1 >> s2;
    int sum = decode(s1)+decode(s2);
    for(int div = 1000; div > 0; div /= 10){
      int num = sum / div;
      sum %= div;
      if(num == 0) continue;
      if(num >= 2 && num <= 9){
        cout << num;
      }
      switch(div){
      case 1000: cout << "m"; break;
      case 100: cout << "c"; break;
      case 10: cout << "x"; break;
      case 1: cout << "i"; break;
      }
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1212
#include<stdio.h>

 int main(void){

int a,b,c,d;

 scanf("%d %d %d",&a,&b,&c);

 if(a>c){

 d=a;

 a=c;

 c=d;

}

 if(a>b){

 d=a;

 a=b;

 b=d;

}

 if(b>c){

 d=b;

 b=c;

 c=d;

}

printf("%d %d %d\n",a,b,c);
return 0;

}

Measured memory_bytes: 596
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main implements Runnable {
	public static void main(String[] args) {
		new Thread(null, new Main(), "", 16 * 1024 * 1024).start();
	}

	public void run() {
		FastScanner scan = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int a = scan.nextInt();
		int b = scan.nextInt();

		int ret = -1;

		if (checkValue(a) && checkValue(b)) {
			ret = a * b;
		}

		out.println(ret);
		out.flush();
	}

	private boolean checkValue(int target) {
		return 1 <= target && target <= 9;
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 22996
import sys
readline = sys.stdin.readline

N,M,X = map(int,readline().split())
books = [None] * N
for i in range(N):
  data = list(map(int,readline().split()))
  cost = data[0]
  point = data[1:]
  books[i] = [cost,point]
  
# M個から1個以上M個以下を選ぶ。選ぶ数でループ
INF = 10 ** 10
ans = INF
import itertools
for i in range(1, N + 1):
  for target in itertools.combinations(books, i):
    skills = [0] * M
    totalcost = 0
    for t in target:
      totalcost += t[0]
      point = t[1]
      for j in range(len(point)):
        skills[j] += point[j]
    if totalcost < ans:
      for j in range(len(skills)):
        if skills[j] < X:
          break
      else:
        ans = totalcost
if ans == INF:
  print(-1)
else:
  print(ans)

Measured memory_bytes: 9192
#include<iostream>
#include<string>
#include<stack>/*** LIFO *** stack<type> var;
push(), top():to get data, pop():to remove, size(), empty() ***/
using namespace std;

#define Fp(I, STAT, END) for(int I = STAT; I < END; I++)
#define Fm(I, STAT, END) for(int I = STAT; I > END; I--)

int main(){
    int a;
    string s;
    cin >> a >> s;
    if(a >= 3200) cout << s << endl;
    else cout << "red" << endl;
}


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

int main (){
int N;
  vector<int>a(101);
cin >> N ;
  for (int i=0;i<N;i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  int Alice = 0,Bob = 0;
  for(int i = 0 ; i<N ;i++){
    if (i % 2 ==0){
      Alice += a.at(i);
    }
    else{
      Bob += a.at(i);
    }
  }
  cout  << Alice - Bob << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int X = sc.nextInt();

		int n = 0;
		int ans = 0;
		for (int i = 0; i < X; i++) {
			n += i + 1;
			if (X <= n) {
				ans = i + 1;
				break;
			}
		}
		// 出力
		System.out.println(ans);
	}
}


Measured memory_bytes: 22228
#include <bits/stdc++.h>
using namespace std;
#define MAX 100007

int partition(int A[], int p, int r){
  int x, i, j;
  x = A[r];
  i = p - 1;
  for(int j = p; j < r; j++){
    if(A[j] <= x){
      i++;
      swap(A[i], A[j]);
    }
  }
  swap(A[i+1], A[r]);
  return i+1;
}


int main(){
  int n, A[MAX], q;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%d", &A[i]);

  q = partition(A, 0, n-1);
  for(int i = 0; i < n; i++){
    if(i==q){
      printf("[%d] ", A[i]);
    } else if(i==n-1){
      printf("%d\n", A[i]);
    } else {
      printf("%d ", A[i]);
    }
  }
  return 0;
}



Measured memory_bytes: 3524
#include<cstdio>

bool done[21][21];
int W,H;
char s[21][21];
bool map[21][21];

void init(){
  for(int i=0;i<21;i++){
    for(int j=0;j<21;j++){
      done[i][j]=false;
      map[i][j]=false;
      s[i][j]=0;
    }}
}

void solve(int h,int w){
  if(s[h][w]=='.' || s[h][w]=='@'){
    map[h][w]=true;
    done[h][w]=true;
    if(h-1 >=0 && done[h-1][w]==false) solve(h-1,w);
    if(h+1 < H && done[h+1][w]==false) solve(h+1,w);
    if(w-1 >=0 && done[h][w-1]==false) solve(h,w-1);
    if(w+1 <W && done[h][w+1]==false) solve(h,w+1);
  }
  else{
    map[h][w]=false;
    done[h][w]=true;
  }

  return;

}
int main(){
  while(1){
    init();
    scanf("%d%d",&W,&H);
    if(W==0 && H==0) break;
    for(int i=0;i<H;i++)
      scanf("%s",&s[i]);
    int sw,sh;
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(s[i][j]=='@'){
          sw=j;
          sh=i;
        }}}

    solve(sh,sw);


    int ans=0;

    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(map[i][j]==true)
          ans++;
      }}

    printf("%d\n",ans);
  }
  return 0;

}

Measured memory_bytes: 1044
[N, T] = [int(i) for i in input().split()]
cmin = 1001
for _ in range(N):
    [c, t] = [int(i) for i in input().split()]
    if t <= T and c <= cmin:
        cmin = c
if cmin == 1001:
    print('TLE')
else:
    print(cmin)

Measured memory_bytes: 3060
N,L = map(int,input().split())

apple = [L+i-1 for i in range(1,N+1)]

for i in range(N):
    flag = True
    for j in range(N-1):
        if abs(apple[j]) > abs(apple[j+1]):
            apple[j],apple[j+1] = apple[j+1],apple[j]
            flag = False
    if flag == True :
        break

del(apple[0])
print(sum(apple))


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

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

    int a, b, k;
    cin >> a >> b >> k;
    rep(i, k)
    {
        if (i % 2)
        {
            b /= 2;
            a += b;
        }
        else
        {
            a /= 2;
            b += a;
        }
    }
    cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>

#define rep(x,to) for(int x=0;x<to;x++)
#define rep2(x,from,to) for(int x=from;x<to;x++)

using namespace std;

typedef pair<int,int> mypair;
int h,w;
string bd[101];

void chil(int y, int x){
int	dx[]={1,-1,0,0};
int	dy[]={0,0,1,-1};
char mrk = bd[y][x];
	stack< mypair > que;
	que.push(mypair(y,x));
	while(!que.empty()){
		int cy = que.top().first;
		int cx = que.top().second;
		que.pop();
		if(bd[cy][cx] == 'C')  continue;
		if(bd[cy][cx] == mrk ) bd[cy][cx] = 'C';
		rep(i,4){
			if(cy+dy[i] < 0 || cy+dy[i] >= h) continue;
			if(cx+dx[i] < 0 || cx+dx[i] >= w) continue;
			if(bd[cy+dy[i]][cx+dx[i]] == mrk ){
				que.push(mypair(cy+dy[i], cx+dx[i]));
			}
		}
	}
//	cout << cnq  << endl;
}


int main(void){

string ws;
	
	while( cin >> h >> w){
		if(h==0 && w==0 || cin.eof()) break;
		rep(i,h)  cin >> bd[i];
		
		int cnt = 0;
		rep(i,h) rep(j,w){
			if(bd[i][j]=='#' || bd[i][j]=='*' || bd[i][j]=='@'){
				cnt++;
				chil(i, j);
			}
		}
		cout << cnt << endl;
//		rep(i,h){ rep(j,w) cout << bd[i][j]; cout << endl; }
	}
	return 0;
	
}

Measured memory_bytes: 1336
#include<bits/stdc++.h>
#define MIN -1000000
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
int V[25];
int C[25];
int ans=0;
int main(void)
{
  int N;
  cin >> N;
  for (int i = 0; i < N; ++i)
    {
      cin >> V[i];
    }
  for (int i = 0; i < N; ++i)
    {
      cin >> C[i];
    }
  for (int i = 0; i < N; ++i)
    {
      if(V[i]>=C[i])
	{
	  ans+=(V[i]-C[i]);
	}
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int d=1e9+7;
int main(){
  int n;
  int64_t ans=1;
  cin >> n;
  for(int i=1;i<=n;i++){
    ans=(i*ans)%d;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3564
#include<bits//stdc++.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define req(i,n) for(int i = 1; i<=n;i++)
using namespace std;
typedef long long int ll;
int main() {
    ll n, now,ans = 1000; cin >> n;
    vector<ll> a(n),dp(100,1000);
    rep(i, n) cin >> a[i];
    req(i, n - 1) {
        dp[i] = dp[i - 1];
        rep(j, i) {
            dp[i] = max(dp[i], dp[j] + (a[i] - a[j]) * (dp[j] / a[j]));
        }
    }cout << dp[n - 1] << endl;
}

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

int main()
{
	long long n, k;
	std::cin >> n >> k;

	std::map<long long, long long> m;

	for (int i = 0; i < n; i++) {
		long long a, b;
		std::cin >> a >> b;

		m[a] += b;
	}

	for (auto it : m) {
		k -= it.second;
		if (k <= 0) {
			std::cout << it.first << std::endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
int main() {
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> A(n);
  rep(i, n) cin >> A[i];
  ll x = 0LL;
  int keta = 0;
  while((k >> keta) > 0) keta++;
  while(keta > 0) {
    keta--;
    int cnt1 = 0;
    rep(i, n) if((A[i] >> keta) & 1) cnt1++;
    if(cnt1 < n / 2 + 1 && x + (1LL << keta) <= k)
      x += (1LL << keta);
  }
  ll ans = 0LL;
  rep(i, n) ans += A[i] ^ x;
  cout << ans << endl;
  return 0;
}

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

int main() {

	int A,B;
	string S,T,U;

	 cin >> S >> T;
	 cin >> A >> B;
	 cin >> U;

	if(S == U){
	A--;
	}else if(T == U){
	B--;
	}

	cout << A <<" "<<B << endl;
	
return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int i,j;
  int n,a[100];
  int v;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&a[i]);
  for(i=0;i<n;i++){
    v=a[i];
    j=i-1;
    while(j>=0 && a[j]>v){
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=v;
    printf("%d",a[0]);
    for(j=1;j<n;j++) printf(" %d",a[j]);  
    printf("\n");
  }
  return(0);
}
  


Measured memory_bytes: 2036
N,X,M = map(int,input().split())
O = [0]*M

XX = X

ans = 0
a = 1
while a <= N:
    if O[X] == 0:
        O[X] = a
    else:
        b = O[X]
        c = a - b
        d = N - (N - b) % c 
        e = N - d
        h = ((N - b) // c)
        #print(*O)
        #print(b,c,d,e,h)
        ans = 0
        X = XX
        for i in range(b):
            ans += X
            X = (X * X) % M
        for i in range(c):
            if i < e:
                ans += (h + 1) * X
            else:
                ans += h * X
            X = (X * X) % M
        print(ans)
        exit()
    ans += X
    X = (X * X) % M
    a += 1

print(ans)

Measured memory_bytes: 66760
import std.stdio;
import std.algorithm;
import std.math;
import std.conv;
import std.string;

T readNum(T)(){
  return readStr.to!T;
}

T[] readNums(T)(){
  return readStr.split.to!(T[]);
}

string readStr(){
  return readln.chomp;
}

void main(){
  auto n = readNum!int;
  auto b = readNums!int;
  int ret;

  foreach(i; 0 .. n-2){
    ret += min(b[i], b[i+1]);
  }

  ret += b[0];
  ret += b[n-2];

  writeln(ret);
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

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


Measured memory_bytes: 3092
import math
N, D = [int(x) for x in input().split()]
ar = [[int(x) for x in input().split()] for i in range(N)]
ans = 0
for i,x in enumerate(ar):
    for y in ar[i+1:]:
        d = 0
        for (a,b) in zip(x,y):
            d += (a-b)*(a-b)
        if (math.sqrt(d) == int(math.sqrt(d))):
            ans += 1
print(ans)

Measured memory_bytes: 3064
<?php
$file_handle = fopen('php://stdin', "r");
//$file_handle = fopen('aoj0001_in.txt', "r");

$top1=0;
$top2=0;
$top3=0;
 
for($i=1; $i<=10; ++$i){
  $stdin = trim(fgets($file_handle));
  if ( $top1===0 || $top1 < $stdin ) {
    $temp1 = $top1;
    $top1 = $stdin;
    $temp2 = $top2;
    $top2 = $temp1;
    $top3 = $temp2;
  } else if ( $top2===0 || $top2 < $stdin ) {
    $temp2 = $top2;
    $top2 = $stdin;
    $top3 = $temp2;
  } else if ( $top3===0 || $top3 < $stdin ) {
    $top3 = $stdin;
  }
}
 
//出力
echo $top1.PHP_EOL;
echo $top2.PHP_EOL;
echo $top3.PHP_EOL;

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

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")

#define DEBUG(x) cout << ">> " << #x << ": " << x << endl;
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define f first
#define s second

const int MOD = 1000000007;
typedef long long ll;
typedef long double ld;

void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}

int main() { _
  int n; cin >> n;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int temp; cin >> temp;
    ans += temp - 1;
  }
  cout << ans << endl;
  return 0;
}

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

int main(void){
    
    unsigned long H,W;
    cin >> H >> W;
    
    if(H%2 == 1 && W%2 == 1){
        if(H == 1 || W == 1){
            cout << 1 << endl;
        }
        else{
            cout<< H*W/2 + 1 <<endl;
        }
        
    }
    else{
        if(H == 1 || W == 1){
            cout << 1 << endl;
        }
        else{
            cout<< H*W/2 <<endl;
        }
        
    }
   
}

Measured memory_bytes: 3548
#include <iostream>
#include<set>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	long long int N, ans = 0;
	cin >> N;
	for (size_t i = 0; i < N; i++)
	{
		long long int l, r;
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
#include <string>
#include <vector>
#include<iostream>
#include <cstdlib>
#include<stdlib.h>
using namespace std;
    

int main(){
    string s;
    cin >> s;
    
    int counter[26] = {0};
    
    for (int i = 0; i < s.length(); i++) {
        counter[s[i] - 'a']++;
    }
    for (auto x: counter) {
        if (x % 2 != 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    
    return 0;
}

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

const int MN = 501234, INF = 1012345678;
int se[MN * 4], seg[MN * 4], lz[MN * 4], n, a[MN], g[MN], b[MN];

void boom(int v) {
	seg[v * 2] += lz[v];
	seg[v * 2 + 1] += lz[v];
	lz[v * 2] += lz[v];
	lz[v * 2 + 1] += lz[v];
	lz[v] = 0;
}
void add(int l, int r, int val, int s = 0, int e = n, int v = 1) {
	if (r <= s || e <= l)
		return;
	if (l <= s && e <= r) {
		seg[v] += val;
		lz[v] += val;
		return;
	}
	boom(v);
	int mid = (s + e) / 2;
	add(l, r, val, s, mid, v * 2);
	add(l, r, val, mid, e, v * 2 + 1);
	seg[v] = min(seg[v * 2], seg[v * 2 + 1]);
}
int get_min(int s = 0, int e = n, int v = 1) {
	if (e - s == 1)
		return s;
	boom(v);
	int mid = (s + e) / 2;
	if (seg[v * 2 + 1] == 0)
		return get_min(mid, e, v * 2 + 1);
	else
		return get_min(s, mid, v * 2 );
}
void add(int p) {
	for (p++; p < MN; p += p & -p)
		se[p]++;
}
int get(int p) {
	int sum = 0;
	for (; p > 0; p -= p & -p)
		sum += se[p];
	return sum;
}
int get(int l, int r) {
	return get(r) - get(l);
}

int main() {
	int k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> g[i];
	for (int i = 0; i < n; i++)
		a[g[i] - 1] = i;
	for (int i = n - 1; i >= 0; i--) {
//		int x;
//     	cerr << max(0, a[i] - k + 1) << ' ' << min(n, a[i] + k) << endl;
		add(a[i], a[i] + 1, get(max(0, a[i] - k + 1), min(n, a[i] + k)));
//		cerr << x << endl;
//     	for (int i = 0; i < n; i++)
//         cerr << get(i, i + 1) << ' ';
//     	cerr << endl;
     	add(a[i]);
	}
//	cerr << endl;
	for (int i = 0; i < n; i++) {
		int v = get_min();
//		cerr << v << endl;
		add(v, v + 1, INF);
		add(max(v - k + 1, 0), min(v + k, n), -1);
		b[v] = n - i;
	}
	for (int i = 0; i < n; i++)
		cout << b[i] << ' ';
}

Measured memory_bytes: 24064
#include <bits/stdc++.h>
#include <numeric>
#include <iomanip>
using namespace std;
    
#define int long long
#define pb push_back
#define ub upper_bound
#define lb upper_bound
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
    
using ll = long long;
const ll INF = LLONG_MAX - 100;
ll mod = 1e9 + 7;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
    
class fact {
public:
    int fmod = 1e9+7;
    vector<int> fac, inv;
    fact (int n, int Mod = 1e9+7) {
        fmod = Mod;
        fac = vector<int>(n,0);
        inv = vector<int>(n,0);
        fac[0] = 1; for (int i = 1; i < n; i++) fac[i] = fac[i-1] * i % fmod;
        for (int i = 0;i < n;i++) inv[i] = fact::POW(fac[i],fmod-2);
    }
    ll nCr(ll n, ll r) {return (fac[n] * inv[r] % fmod) * inv[n-r] % fmod;}
    ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%fmod;}a = a * a%fmod; b >>= 1;}return c;}
};
    
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return a * b / GCD(a, b);}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%mod;}a = a * a%mod; b >>= 1;}return c;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}
bool isSqrt(ll a) {return pow(sqrt(a),2) == a ? 1 : 0;}
void YesNo(bool a) {if (a) cout << "Yes"; else cout << "No"; cout << endl;}
void yesno(bool a) {if (a) cout << "yes"; else cout << "no"; cout << endl;}
void YESNO(bool a) {if (a) cout << "YES"; else cout << "NO"; cout << endl;}
int poorpow(int b, int a) {
    int tmp = 1;
    REP (i,a) {
        tmp *= b;
    }
    return tmp;
}


bool solve() {
    int a,b,c; cin >> a >> b >> c;
    cout << min(c,b/a) << endl;
}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dl double long
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rrep(i, m, n) for(ll i = (ll)(m); i > (ll)(n); --i)
const ll MOD = 1000000007;
const double pi = 3.14159265358979323846;

int main(void){
    ll a, b, n, x;
    cin >> a >> b >> n;
    if(n < b) x = n;
    else x = b-1;
    cout << (a*x/b - a * (x/b)) << endl;
    return 0;
}

Measured memory_bytes: 3588
N=int(input())
s=[input() for i in range(N)]
M=int(input())
t=[input() for i in range(M)]
s2=list(set(s))
counter=0
for i in range(len(s2)):
    if s.count(s2[i])-t.count(s2[i])>counter:
        counter=s.count(s2[i])-t.count(s2[i])

print(counter)


Measured memory_bytes: 9196
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, start, end) for(int i = start; i < (int)(end); ++i)
double a[101];
int main(){
    double n, m;
    cin >> n >> m;
    rep(i,0,n) cin >> a[i];
    double sum = 0;
    rep(i,0,n) sum += a[i];
    int cnt = 0;
    rep(i,0,n){
        if(sum/4/m <= a[i]){
            cnt++;
        }
    }

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

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

int main(){
  long long n,m;
  cin >> n >> m;
  pair<long long,long long> a[n];
  for (int i=0;i<n;i++){
    cin >> a[i].first >> a[i].second;
  }
  sort(a,a+n);
  long long total = 0;
  for (int i=0;i<n;i++){
    if (m > a[i].second) total += a[i].first*a[i].second;
    else total += a[i].first*m;
    m -= a[i].second;
    if (m <= 0) break;
  }
  cout << total << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
typedef int TInt;
typedef std::vector<TInt> TList;
TList Input()
{
    int Count;
    std::cin >> Count;
    TList List(Count);
    for(int i = 0; i < Count; ++i){
        std::cin >> List[i];
    }
    return List;
}
// ?????????????????°??????????????????
struct TIsDivisibility
{
    const TInt FValue;
    TIsDivisibility(const TInt& Value)
     : FValue(Value){}
    bool operator()(TInt Prime)
    {
        return FValue % Prime == 0;
    }
};
bool IsPrime(TInt Value, const TList& Prime)
{
    TInt Max = std::sqrt(Value);
    for(TList::const_iterator It = Prime.begin();
        It != Prime.end() && *It <= Max;
        ++It)
    {
        if(Value % (*It) == 0) return false;
    }
    return true;
}
TList GetPrimeList(TInt Max)
{
    TList Prime;
    Prime.reserve(Max);
    Prime.push_back(2);
    for(TInt i = 3; i <= Max; i += 2){
        if(IsPrime(i, Prime)){
            Prime.push_back(i);
        }
    }
    return Prime;
}
struct TIsPrimeFullList
{
    const TList& FPrime;
    TIsPrimeFullList(const TList& PrimeFullList)
     : FPrime(PrimeFullList){}
    bool operator()(const TInt& Value)
    {
        return std::binary_search(FPrime.begin(), FPrime.end(), Value);
    }
};
struct TIsPrimeRootList
{
    const TList& FPrime;
    TIsPrimeRootList(const TList& PrimeRootList)
     : FPrime(PrimeRootList){}
    bool operator ()(const TInt& Value)
    {
        return IsPrime(Value, FPrime);
    }
};
void Output(const TList& List)
{
    for(TList::const_iterator It = List.begin();
        It != List.end();
        ++It)
    {
        std::cout << *It << std::endl;
    }
}
int main()
{
    TList Values = Input();
    std::sort(Values.begin(), Values.end());
    TInt Max = *Values.rbegin();
    // std::cout << "Max:" << Max << std::endl;
    TList::iterator Root = std::lower_bound(Values.begin(), Values.end(), std::sqrt(Max));
    // std::cout << "Root" << *Root << std::endl;
    TList Prime = GetPrimeList(*Root);
    // Output(Prime);
    // std::cout << "Size:" << Prime.size() << std::endl;
    int Count = std::count_if(Values.begin(), Root, TIsPrimeFullList(Prime));
    Count += std::count_if(Root, Values.end(), TIsPrimeRootList(Prime));
    std::cout << Count << std::endl;
    return 0;
}

Measured memory_bytes: 1264
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = Integer.parseInt(s.next());
        int q = Integer.parseInt(s.next());
        long[] ar = new long[n+1];
        TreeSet<Long> set = new TreeSet<Long>();
        for(int i = 1; i <= n; i++){
            long key = 0 * 1000001 + (n-i);
            set.add(key);
        }
        for(int i = 0; i < q; i++){
            int a = Integer.parseInt(s.next());
            int v = Integer.parseInt(s.next());
            long old_key = ar[a] * 1000001 + (n-a);
            ar[a] += v;
            long new_key = ar[a] * 1000001 + (n-a);
            set.remove(old_key);
            set.add(new_key);
            long max_a = n-(long)(set.last()) % 1000001;
            long max_v = (long)(set.last()) / 1000001;
            System.out.println(max_a + " " + max_v);
        }
    }
}

Measured memory_bytes: 180380
#include<iostream>
#include<algorithm>

int main(){
  int n;
  int i;
  std::cin >> n;
  
  int v[n];
  double w[n];
  for(i=0;i<n;i++){
    std::cin >> v[i];
    w[i] = (double)v[i];
  }
  std::sort(w,w+n);
  
  for(i=0;i<n-1;i++){
   w[i+1] = (w[i] + w[i+1])/2;
  }
  
  std::cout << w[n-1];
}

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

struct Dsu {
  vector<int> fa, szb, szw;
  Dsu(int n) : fa(n), szb(n, 0), szw(n, 0) {
    iota(fa.begin(), fa.end(), 0);
  }
  int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
  void unite(int x, int y) {
    int a = find(x);
    int b = find(y);
    if (a != b) {
      fa[a] = b;
      szb[b] += szb[a];
      szw[b] += szw[a];
    }
  }
};

signed main() {
  ios::sync_with_stdio(false);

  int H, W;
  cin >> H >> W;

  vector<string> S(H);
  for (int i = 0; i < H; ++i) cin >> S[i];

  Dsu dsu(H * W);
  for (int i = 0; i < H * W; ++i) {
    dsu.szw[i] = S[i / W][i % W] == '.';
    dsu.szb[i] = S[i / W][i % W] == '#';
  }
  vector<int> vis(H * W);
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (vis[i * W + j]) continue;
      queue<int> que;
      que.push(i * W + j);
      vis[i * W + j] = 1;
      while (que.size()) {
        int x = que.front() / W;
        int y = que.front() % W;
        que.pop();
        static const int dx[] = {0, 1, 0, -1};
        static const int dy[] = {1, 0, -1, 0};
        for (int di = 0; di < 4; ++di) {
          int nx = x + dx[di];
          int ny = y + dy[di];
          if (nx < 0 || H <= nx || ny < 0 || W <= ny) continue;
          if (vis[nx * W + ny]) continue;
          if (S[nx][ny] == S[x][y]) continue;
          que.push(nx * W + ny);
          vis[nx * W + ny] = 1;
          dsu.unite(i * W + j, nx * W + ny);
        }
      }
    }
  }

  int64_t ans = 0;
  for (int i = 0; i < H * W; ++i) {
    if (dsu.find(i) == i) {
      int szw = dsu.szw[i];
      int szb = dsu.szb[i];
      ans += 1LL * szw * szb;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4480
#include<iostream>
#include<vector>
#define lli long long int
#include<climits>
#include<unordered_map>
#include<algorithm>
#include<bitset>
#include<map>
#include<cmath>
#include<queue>
#define pb push_back
#define N (int)(1e5)
using namespace std;
using namespace std;
int main()
{
    int h,n;
    int i,j;
    cin>>h>>n;
    vector<vector<lli>>dp(n,vector<lli>(h+1));
    vector<int>att(n);
    vector<int>pt(n);
    for(i=0;i<n;i++){ cin>>att[i];cin>>pt[i];}
    for(i=0,j=0;i<n;i++) dp[i][j]  = 0;
    vector<lli>mins(h+1);
    mins[0] = 0;
    
    for(j=1;j<=h;j++)
    {
        mins[j] = LLONG_MAX;
        for(i=0;i<n;i++)
        {
            if(j-att[i]>=0) dp[i][j] = pt[i] + mins[j-att[i]];
            else dp[i][j] = pt[i];
            
            if(dp[i][j]<mins[j])  mins[j] = dp[i][j];
        }
        
    }
    
    
//    for(int i=0;i<n;i++)
//    {
//        for(int j=0;j<=h;j++)
//        {
//            cout<<dp[i][j]<<" ";
//
//        }
//        cout<<endl;
//    }
//
    
    
    
    cout<<mins[h]<<endl;
    
    
    
    

}



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

using ll = long long;
using ull = unsigned long long;
using st = string;
using ch = char;
using db = double;
using bl = bool;
using vll = vector<long long>;
using vdb = vector<db>;
using vvll = vector<vll>;
using vst = vector<st>;
using vch = vector<char>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (ll i = (ll)(m); i < (ll)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b;return true;} return false;}
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b;return true;} return false;}
const ll mod = 1000000007;
const ll inf = 1LL << 60;

int main(){
	ll n, m;
	cin >> n >> m;
	vvll graph(n);
	rep(i, 0, m){
		ll u, v;
		cin >> u >> v;
		u--; v--;
		graph.at(u).push_back(v);
	}
	ll s, g;
	cin >> s >> g;
	s--; g--;

	queue<pll> que;
	vvll dis(n, vll(3, -1));
	dis.at(s).at(0) = 0;
	que.push(make_pair(s, 0));
	while(que.size()){
		ll v = que.front().first, mod3 = que.front().second;
		que.pop();
		vrep(nv, graph.at(v)) if(dis.at(nv).at((mod3 + 1) % 3) == -1) {
			que.push(make_pair(nv, (mod3 + 1) % 3));
			dis.at(nv).at((mod3 + 1) % 3) = dis.at(v).at(mod3) + 1;
		}
	}
	cout << (dis.at(g).at(0) == -1 ? dis.at(g).at(0) : dis.at(g).at(0) / 3) << endl;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define rep(i,n,z) for(int i=z;i<n;i++)
#define rrep(i,z) for(int i=z;i>=0;i--)
#define nl cout<<endl
#define vi vector<int>
#define vlli vector<long long int>
#define umap unordered_map
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define ipair pair <int,int>
#define llipair pair <lli,lli>
#define pq priority_queue
#define displaymatrix(a,m,n) for(int i=0;i<m;i++){for(int j=0;j<n;j++)cout<<a[i][j]<<" ";cout<<endl;}
#define printarray(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}nl;
#define vinput(a,n) vlli a(n);rep(i,n,0)cin>>a[i]
#define ainput(a,n) rep(i,n,0)cin>>a[i]
#define SO(a) sort(a.begin(),a.end())
#define all(x) (x).begin(),(x).end()
#define SOP(a,comp) sort(a.begin(),a.end(),comp)
#define inf INT_MAX
#define endl '\n'
 
int main()
{
    fastio;
    lli n;
    cin>>n;
    lli N= n;

    n = (n/1000)*1000;
    if(n < N)n += 1000;
    cout<<n-N<<endl;
}

Measured memory_bytes: 3652
n,d=map(int, input().split())
xd = [list(map(int, input().split())) for _ in range(n)]
import math
ans = 0
for i in range(len(xd)):
    for j in range(len(xd)):
        d = 0
        if i == j:
            continue
        for k in range(len(xd[i])):
            d += abs(xd[i][k]-xd[j][k])**2
        if math.sqrt(d).is_integer():
            ans += 1
print(int(ans/2))

Measured memory_bytes: 3064
h, w = map(int, input().split())
a = [input().split() for i in range(h)]
 
for i in range(h):
    a[i].insert(0, "#")
    a[i].append("#")
 
a.insert(0, ["#"*(w+2)])
a.append(["#"*(w+2)])

for i in a:
    print("".join(map(str,i)))

Measured memory_bytes: 3060
words = lambda t : list(map(t, input().split()))
s = input()
ans = 0
prev = "#"
i = 0
while i < len(s)-1:
    ans += 1
    if s[i] == prev:
        prev = s[i] + s[i+1]
        i += 2
    else:
        prev = s[i]
        i += 1
if i == len(s) - 1 and prev != s[i]:
    ans += 1

print(ans)


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

using namespace std;

pair<int, int> edg[100000];
int grp[100001], grpsz[100001];

int find(int now) {
	if (grp[now] == now)
		return now;

	return grp[now] = find(grp[now]);
}

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
		
	for (int i = 0;i < m;++i)
		scanf("%d %d", &edg[i].first, &edg[i].second);

	for (int i = 1;i <= n;++i) {
		grp[i] = i;
		grpsz[i] = 1;
	}

	long long ans = (long long)n * (n - 1) / 2;
	stack<long long> anss;
	for (int i = m - 1;i >= 0;--i) {
		anss.push(ans);

		int u = find(edg[i].first), v = find(edg[i].second);

		if (u == v)
			continue;

		ans -= (long long)grpsz[u] * grpsz[v];

		grpsz[v] += grpsz[u];
		grp[u] = v;
	}

	while (!anss.empty()) {
		printf("%lld\n", anss.top());
		anss.pop();
	}

	return 0;
}

Measured memory_bytes: 3484
N, K = [int(x) for x in input().split()]
arr = [0] * (10**5+1)
for _ in range(N):
    a, b = [int(x) for x in input().split()]
    arr[a] += b

th = 0
for i in range(1, 10**5+1):
    if arr[i] != 0:
        th += arr[i]
    if th >= K:
        print(i)
        exit()

Measured memory_bytes: 5848
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)


constexpr lint MOD = 1000000007;
vector<vector<lint>> matmul(const vector<vector<lint>> &A, const vector<vector<lint>> &B, lint mod)
{
    int H = A.size(), W = B[0].size(), K = B.size();
    vector<vector<lint>> C(H, vector<lint>(W));
    REP(i, H) REP(j, W) REP(k, K) (C[i][j] += A[i][k] * B[k][j]) %= mod;
    return C;
}
vector<lint> matmul(const vector<vector<lint>> &A, const vector<lint> &v, lint mod)
{
    vector<lint> res(A.size());
    REP(i, A.size()) REP(j, v.size()) (res[i] += A[i][j] * v[j]) %= mod;
    return res;
}
vector<vector<lint>> matpower(vector<vector<lint>> X, lint n, lint mod)
{
    vector<vector<lint>> res(X.size(), vector<lint>(X.size()));
    REP(i, res.size()) res[i][i] = 1;
    while (n)
    {
        if (n & 1) res = matmul(res, X, mod);
        X = matmul(X, X, mod); n >>= 1;
    }
    return res;
}

int N, M;
vector<lint> X;


int main()
{
    vector<vector<lint>> trans{
        {1, 1, 2, 1},
        {1, 1, 2, 1},
        {1, 0, 1, 1},
        {1, 0, 0, 1}};

    cin >> N >> M;
    X.resize(M + 1);
    REP(i, M) cin >> X[i + 1];
    X.push_back(N);

    vector<lint> st{1, 0, 0, 0};
    FOR(i, 1, X.size())
    {
        st = matmul(matpower(trans, X[i] - X[i - 1], MOD), st, MOD);
        st[0] = 0;
    }
    cout << st[1] << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define fore(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define rfore(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);--i)
#define rrep(i,n) rfore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

ll par[100005];
ll find(ll x){
    if(par[x]<0)return x;
    return par[x]=find(par[x]);
}
void unite(ll x,ll y){
    x=find(x),y=find(y);
    if(x==y)return;
    par[y]=x;
}

struct Town {
    ll i,x,y;
    Town(ll i,ll x,ll y):i(i),x(x),y(y){}
};

void solve(){
    ll n;cin>>n;
    vector<Town> a;
    rep(i,n){
        ll x,y;cin>>x>>y;
        a.emplace_back(i,x,y);
    }
    vector<Town> cand;
    sort(all(a),[](Town &t1,Town &t2){
        return t1.x<t2.x;
    });
    rep(i,n-1){
        cand.emplace_back(a[i+1].x-a[i].x,a[i+1].i,a[i].i);
    }
    sort(all(a),[](Town &t1,Town &t2){
        return t1.y<t2.y;
    });
    rep(i,n-1){
        cand.emplace_back(a[i+1].y-a[i].y,a[i+1].i,a[i].i);
    }
    sort(all(cand),[](Town &t1,Town &t2){
        return t1.i<t2.i;
    });

    memset(par,-1,sizeof(par));
    ll ans=0;
    for(Town t:cand){
        if(find(t.x)!=find(t.y)){
            ans+=t.i;
            unite(t.x,t.y);
        }
    }
    cout<<ans<<endl;
}

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


Measured memory_bytes: 10864