akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

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

fn main() {
    input! {
        n: usize, w: usize,
        goods: [(usize, usize); n]
    }

    let mut dp = vec![0; w + 1];

    for &(weight, value) in &goods {
        for i in (weight..w + 1).rev() {
            dp[i] = std::cmp::max(dp[i], dp[i - weight] + value);
        }
    }
    println!("{}", dp[w]);
}


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

int main()
{
   string n;
   cin >> n;
   bool ok = false;
   for(int i = 0; i < 3; i++)
   {
       if(n[i] == '7')
       {
           ok = true;
           break;
       }
   }
   if(ok== true)
   {
       cout << "Yes" << endl;
   }
   else
   {
       cout << "No" << endl;
   }
    return 0;
}


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

using namespace std;

const long long INF = (long long) 1e15;

long long find(set<long long> &s, long long pos, int dir)
{
    if (s.count(pos)) return pos;
    auto it = s.lower_bound(pos);
    if (dir) {
        if (it == s.begin()) return *s.begin();
        else return *(--it);
    } else {
        if (it == s.end()) return *s.rbegin();
        else return *it;
    }
}

void solve(long long A, long long B, long long Q, set<long long> s, set<long long> t, vector<long long> x)
{
    for(int i = 0 ; i < Q ; i++){
        long long ans = INF, cur, p;
        for (int dir = 0; dir <= 1; ++dir) {
            p = find(s, x[i], dir);
            ans = min(ans, abs(x[i]-p) + min(abs(p-find(t, p, 0)), abs(p-find(t, p, 1))));
        }
        for (int dir = 0; dir <= 1; ++dir) {
            p = find(t, x[i], dir);
            ans = min(ans, abs(x[i]-p) + min(abs(p-find(s, p, 0)), abs(p-find(s, p, 1))));
        }

        cout << ans << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long A;
    cin >> A;
    long long B;
    cin >> B;
    long long Q;
    cin >> Q;
    long long v;
    set<long long> s;
    for(int i = 0 ; i < A ; i++){
        cin >> v;
        s.insert(v);
    }
    set<long long> t;
    for(int i = 0 ; i < B ; i++){
        cin >> v;
        t.insert(v);
    }
    vector<long long> x(Q);
    for(int i = 0 ; i < Q ; i++){
        cin >> x[i];
    }
    solve(A, B, Q, move(s), move(t), move(x));
    return 0;
}


Measured memory_bytes: 11520
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define CMAX(m, x)  m = max(m,x);
#define CMIN(m, x)  m = min(m,x);
#define itn int
typedef long long lint;
const int INF = 1e9;
const lint LINF = 1e18;
int main(){
    int s,w;
    cin >> s >> w;
    if(s > w)
        cout << "safe" << endl;
    else
        cout << "unsafe" << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int main(){
    unsigned long long ina, ans;
    double inb;
    cin >> ina >> inb;
    int int_inb = round(inb*100);
    ans = (ina * int_inb)/100;
    cout << ans << endl;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    int ans=1e9, z;
    z = max(x,y);
    for(int i=0;i<=2*z;i++){
        int ab = a*max(0, x-i) + b*max(0,y-i) + i*2*c;
        ans = min(ab, ans);
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
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;}

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

V<V<V<ll> > > edges;
vll rb, d;
ll bmin=HIGHINF, rmin=HIGHINF, tmp;
bool change=false;

bool dfs(ll i) {
    if (rb[i]==0) chmin(rmin, d[i]);
    else chmin(bmin, d[i]);
    for (vll vs: edges[i]) {
        ll s=vs[0], v=vs[1];
        if (rb[v]==-1) {
            rb[v] = (rb[i]+1) % 2;
            d[v] = s - d[i];
            if (!dfs(v)) return false;
        }
        if (rb[i] != rb[v]) { if (d[i]+d[v] != s) return false;}
        else {
            ll val;
            if (rb[i]==0) val = (s-d[i]-d[v]);
            else val = -(s-d[i]-d[v]);
            if (!change) {
                tmp=val; change=true;
            }
            if (val%2==1 || tmp!=val) return false;
        }
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m; cin >> n >> m;
    edges.resize(n);
    REP(i, m) {
        ll u, v, s; cin >> u >> v >> s;
        vll sv(2); sv[0]=s; sv[1]=v-1;
        edges[u-1].push_back(sv);
        sv[1] = u-1;
        edges[v-1].push_back(sv);
    }
    rb.resize(n, -1);
    rb[0] = 0;
    d.resize(n, 0);
    if (!dfs(0)) cout << 0 << '\n';
    else {
        if (change) {
            if (tmp/2+rmin<=0 || tmp/2+bmin<=0) cout << 0 << '\n';
            else cout << 1 << '\n';
        } else cout << max(0LL, rmin+bmin-1) << '\n';
    }
    return 0;
}


Measured memory_bytes: 25984
x,y = map(int,input().split())

a = y-x if y-x >= 0 else float("inf")
b = y+x+1 if y+x >= 0 else float("inf")
c = x-y+2 if x-y >=0 else float('inf')
d = -(y+x)+1 if x+y <=0 else float('inf')

print(min(a,b,c,d))



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

typedef signed long long ll;
typedef vector <int> vi; 
const int MX = 1e4 + 5;
int dis[MX];
vi G[MX];

int main() {
	int h, a;
	cin >> h >> a;
	cout << h / a + ((h % a != 0) ? 1 : 0) << endl;
	
    return 0;
}

Measured memory_bytes: 512
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, T = nm()
    C = []
    for _ in range(n):
        c, t = nm()
        if t <= T:
            C.append(c)
    print(min(C) if C else 'TLE')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9080
#include <array>
#include <climits>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int main() {
    // input
    int n; scanf("%d", &n);
    vector<array<int, 10> > f(n);
    repeat (i, n) repeat (j, 10) scanf("%d", &f[i][j]);
    vector<array<int, 11> > p(n);
    repeat (i, n) repeat (j, 11) scanf("%d", &p[i][j]);
    // solve
    int result = INT_MIN;
    repeat_from (s, 1, 1 << 10) {
        int acc = 0;
        repeat (i, n) {
            int conflict = 0;
            repeat (j, 10) if (s & (1 << j)) {
                conflict += f[i][j];
            }
            acc += p[i][conflict];
        }
        setmax(result, acc);
    }
    // output
    printf("%d\n", result);
    return 0;
}


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

using namespace std;

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

    const long Size = 100000;
    int N; cin>>N;
    map<long, set<long>> graph;
    vector<pair<long,long>> pos;
    for (long i = 0; i < N; i++) {
        long x,y; cin>>x>>y;
        x--;y--;
        graph[x].insert(Size+y);
        graph[Size+y].insert(x);
        pos.emplace_back(x,y);
    }


    set<long> node;
    long ans = 0;
    for (size_t i = 0; i < Size*2; i++) {
        if (graph[i].empty() or node.find(i) != node.end())
            continue;
        set<long> xx, yy;
        function<void(long)> find = [&](long p) {
            if (node.find(p) != node.end())
                return;
            node.insert(p);
            if (p < Size)
                xx.insert(p);
            else
                yy.insert(p);
            for (auto n : graph[p])
                find(n);
            return;
        };
        find(i);
        long cnt = 0;
        for (auto& p : pos) {
            if (xx.find(p.first) != xx.end() or yy.find(p.second) != yy.end())
                cnt++;
        }
        ans += xx.size()*yy.size()-cnt;
    }
    cout << ans << endl;


    return 0;
}


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

using namespace std;

int main(){
  int n,sum = 0,sumpow = 0;
  cin >> n;
  for(int i = 0;i < n;i++){
    int x;cin >> x;
    sum += x;
    sumpow += x*x;
  }
  cout << (sum*sum - sumpow)/2;
  return 0;
}

Measured memory_bytes: 256
S = input()
c = True
for i in range (len(S)//2):
  if S[i]==S[len(S)//2-i-1]==S[len(S)//2+1+i]==S[len(S)-i-1]:
    c = True
  else:
    c = False
    break
if (c):
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
N = int(input().strip())

name = ''
next_N = N
for i in range(11):
    m = next_N % 26
    next_N //= 26

    if m > 0:
        name = chr(0x60 + m) + name
    elif m == 0:
        name = 'z' + name
        next_N -= 1

    if next_N <= 0:
        break

print(name)


Measured memory_bytes: 9168
#include <iostream>

using namespace std;

int main() {
	int s, m, h;
	cin >> s;
	h = s / 3600;
	s %= 3600;
	m = s / 60;
	s %= 60;
	
	cout << h << ":" << m << ":" << s << endl;

	return 0;
}


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

int main() {
  int N;
  string S;
  cin >> N >> S;
  
  vector<int> count(N, 0);
  for (int i = 1; i < N; i++) {
    if (S[i] == 'E') count.at(0)++;
  }

  for (int i = 1; i < N; i++) {
    count.at(i) = count.at(i - 1);
    if (S[i - 1] == 'W') count.at(i)++;
    if (S[i] == 'E') count.at(i)--;
  }
  
  int ans = 1e6;
  for (int i = 0; i < N; i++) {
    if (count.at(i) < ans) ans = count.at(i);
  }
  
  cout << ans << endl;
  
  return 0;
}

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

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, ll> para;
const ll inf = 1e9 + 7;
const ll maxN = 5e6 + 5;
const ll MOD = 998244353;

ll a, b;
ll gcd(ll a, ll b) {
	while (b != 0) {
		ll c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> a >> b;
	cout << (a * b) / gcd(a, b);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
  public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

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

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

void solve(long long N, std::vector<long long> H)
{
    int cnt = 0;
    ll maxHeight = -1;
    for (int i = 0; i < N; i++)
    {
        if (maxHeight <= H[i])
        {
            maxHeight = max(maxHeight, H[i]);
            cnt++;
        }
    }
    cout << cnt << endl;
}

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


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define LARGE 100


int V,E;
int color=0;

typedef struct list{
	int id;
	struct list *next;
}list;


list * makelist(int x){
	list *new=malloc(sizeof(list));
	new->id=x;
	new->next=NULL;
	return new;
}

void list_insert(list* L[],int x,list *new){
	list **p=&L[x];
	
	while((*p)!=NULL){
		p=&((*p)->next);
	}
	(*p)=new;
	
	return;
}

int push(int stack[],int x,int top){
	stack[top++]=x;
	return top;
}

int pop(int stack[],int *top){
	(*top)--;
	return stack[*top];
}

int dfs(int C[],int x,list* L[]){
	int stack[LARGE];
	int top=0;
	int temp;
	list *p;
	
	color++;
	top=push(stack,x,top);
	while(top>0){
		temp=pop(stack,&top);
		if(C[temp]==0)C[temp]=color;
		p=L[temp];
		while(p!=NULL){
			if(p->id==x)return 0;
			if(C[p->id]==0){
				top=push(stack,p->id,top);
				C[p->id]=color;
			}
			p=p->next;
		}
	}
	
	return 1;
}

int main(){
	int i,j;
	int s,t;
	int x,y;
	list *L[LARGE];
	list *new;
	int C[LARGE];
	int flg;
	
	scanf("%d %d",&V,&E);
	
	for(i=0;i<V;i++){
		L[i]=NULL;
		C[i]=0;
	}
	
	for(i=0;i<E;i++){
		scanf("%d %d",&s,&t);
		new=makelist(t);
		list_insert(L,s,new);
	}
	
	for(i=0;i<V;i++){
		for(j=0;j<V;j++)C[j]=0;
		flg=dfs(C,i,L);
		if(!flg){
			printf("1\n");
			break;
		}
	}
	
	if(flg)printf("0\n");
	
	return 0;
	
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
int n,m,a[305][305];


int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
	int nxt = 1;
	for(int j=1;j<=m;j++){
		int pck = -1;
		for(int x=nxt;x<=n;x++){
			if(a[x][j] == 1){
				pck = x; break;
			}
		}
		if(pck == -1) continue;
		repn(j,m) swap(a[nxt][j],a[pck][j]);
		for(int x=nxt+1;x<=n;x++){
			if(a[x][j] == 1){
				for(int jj=j;jj<=m;jj++){
					a[x][jj] ^= a[nxt][jj];
				}
			}
		}
		nxt++;
	}
	int ans = n+1-nxt; 
	ll A = 1;
	rep(i,ans) A = A*2LL%mod;
	ll B = 1;
	rep(i,n) B = B*2LL%mod;
	B -= A;
	rep(i,m-1) B = B*2LL%mod;
	cout << (B%mod+mod)%mod << endl;
}

Measured memory_bytes: 640
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    x1, y1, x2, y2 = LI()

    p2p3_x = y1 - y2
    p2p3_y = x2 - x1
    x3 = x2 + p2p3_x
    y3 = y2 + p2p3_y
    p3p4_x = x1 - x2
    p3p4_y = y1 - y2
    x4 = x3 + p3p4_x
    y4 = y3 + p3p4_y

    print(x3, y3, x4, y4)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9992
N = int(input())
ls_A = list(map(int,input().split()))
ls_B = list(map(int,input().split()))
ls_C = list(map(int,input().split()))

#追加点なしで考える
manzoku = sum(ls_B)  #全種類食べる

#追加点
for i in range(N-1):
    if ls_A[i+1] == ls_A[i]+1:
        manzoku += ls_C[ls_A[i]-1]

print(manzoku)


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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define per(i,n) for(ll i = n-1; i >= 0; i--)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define PER(i,n) for(ll i = n; i >= 1; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
using vP = vector<P>;
using vPP = vector<vP>;
using vPl = vector<Pl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }



int main(){
  int d;
  cin >> d;
  int k = 26;
  vi c(k);
  rep(i,k) cin >> c[i];
  vii s(d,vi(k));
  rep(i,d)rep(j,k) cin >> s[i][j];
  rep(i,d) cout << 1 << endl;
}

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

using namespace std;

long long int dp[100005][105];

pair<int,int>jinis[105];

void init(){
 memset(dp,-1,sizeof(dp));
}

long long solve(int vleft, int cur, int n){
 if(cur==n){
   if(vleft==0)return 0;
   return (long long)2000000000;
 }
 if(dp[vleft][cur]!=-1)return dp[vleft][cur];
 long long ret1 = 0, ret2 = 0;

 ret1 = (long long)jinis[cur].first + solve(max(0,vleft-jinis[cur].second),cur+1,n);

  ret2 = solve(vleft, cur+1, n);
  return dp[vleft][cur] = min(ret1,ret2);
}

int main(){
  //freopen("input.txt","r",stdin);
  int n,w;
  cin>>n>>w;
  int hi = 0;
  for(int i = 0; i<n; ++i){
   cin>>jinis[i].first>>jinis[i].second;
    hi = hi+jinis[i].second;
  }

  int lo = 0;
  init();

  for(;hi;hi--){
    long long  xx=solve(hi,0,n);
    if(xx<=(long long )w)return cout<<hi<<endl,0;
  }

  cout<<0<<endl;


  //for()
//  while(lo+1<hi){
//     int mid = (lo+hi)/2;
//    //init();
//     if(solve(mid,0,n)<=w)lo = mid;
//    else hi = mid;
//  }
//  long long lw = solve(hi,0,n);
//  if(lw<=w){
//   cout<<hi<<"\n";
//  }
//  else{
//  		cout<<lo<<"\n";
//  }
  //cout<<solve(w,0,n)<<"\n";
  return 0;
}


Measured memory_bytes: 82816
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
      
      	if((a==(b+c))||(b==(a+c))||(c==(a+b))){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
    }
}

Measured memory_bytes: 20820
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> X(N);
    REP(i, 0, N) cin >> X[i];

    vector<int> Y = X;
    sort(ALL(Y));
    int l = Y[N / 2 - 1], r = Y[N / 2];
    
    REP(i, 0, N) {
        if (X[i] < r) cout << r << endl;
        else cout << l << endl;
    }
    return 0;
}

Measured memory_bytes: 3712
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

class union_find {
private:
	vector<int> uf;

public:
	union_find(int n) {
		uf.resize(n, -1);
	}
	
	inline int find(int x) {
		return uf[x] < 0 ? x : uf[x] = find(uf[x]);
	}
	
	inline bool unite(int x, int y) {
		x = find(x);
		y = find(y);
		if(x == y)
			return false;
		
		if(uf[x] > uf[y])
			swap(x, y);
		
		else if(uf[x] == uf[y])
			--uf[x];
		
		uf[y] = x;

		return true;
	}
};
typedef double weight;

struct edge {
	int u, v;
	weight cost;
	edge(int u, int v, weight c):u(u), v(v), cost(c){}

	bool operator< (const edge& o) const {
		return cost < o.cost;
	}
};

int n;
vector<edge> es;

weight kruskal() {
	sort(es.begin(), es.end());
	union_find uf(n);

	weight res = 0;
	for(int i = 0; i < (int)es.size(); ++i)
		if(uf.unite(es[i].u, es[i].v))
			res += es[i].cost;

	return res;
}

inline weight dist(weight x1, weight y1, weight z1, weight x2, weight y2, weight z2) {
	const weight dx = x1 - x2, dy = y1 - y2, dz = z1 - z2;
	return sqrtl(dx * dx + dy * dy + dz * dz);
}

int main() {
	while(scanf("%d", &n), n) {
		vector<weight> x(n), y(n), z(n), r(n);
		for(int i = 0; i < n; ++i)
			scanf("%lf %lf %lf %lf", &x[i], &y[i], &z[i], &r[i]);

		es.clear();
		for(int i = 0; i < n; ++i) {
			for(int j = i + 1; j < n; ++j) {
				const weight cost = max<weight>(0.0, dist(x[i], y[i], z[i], x[j], y[j], z[j]) - r[i] - r[j]);
				es.push_back(edge(i, j, cost));
			}
		}

		printf("%.3lf\n", kruskal());
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1268
import bisect
import copy
import heapq
import math
import sys
import random
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,s=map(int,input().split())
a=list(map(int,input().split()))

dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1

for i in range(n):
    for j in range(s+1):
        dp[i+1][j]+=2*dp[i][j]
        dp[i+1][j]%=mod
        if j+a[i]<=s:
            dp[i+1][j+a[i]]+=dp[i][j]
            dp[i+1][j+a[i]]%=mod

print(dp[n][s])

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

#define NAME "test"
#define show(x) cout << (#x) << " is " << (x) << endl
#define ll long long
#define ms(arr,val) memset(arr,val,sizeof(arr))
#define len length()

const int maxn = 50;
double a[maxn];
int main(){
    //ifstream cin(NAME".inp");
    //ofstream cout(NAME".out");
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    double ans = 0;
    ans = a[0];
    for(int i=1;i<n;i++) ans = (ans+a[i])/2.0;
    cout<<ans;

}


Measured memory_bytes: 3756
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#define ll long long
using namespace std;
const int maxn = 100005;
const int mod = 1e9+7;

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

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i = 0; i <= n; i++)
        fa[i] = i;
    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int aa = find(a);
        int bb = find(b);
        if(aa != bb){
            fa[aa] = bb;
            ans++;
        }
    }
    printf("%d\n", n - 1 - ans);
    return 0;
}

Measured memory_bytes: 4212
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void print_list(int *A,int n){
  int i;
  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i!=n-1)
      printf(" ");
    else
      printf("\n");
  }
}

void insertion_sort(int *A,int n){
  int i,j,temp;
  print_list(A,n);//??¨?????¨
  for(i=1;i<n;i++){
    temp=A[i];
    j=i-1;
    while(j>=0&&A[j]>temp){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=temp;
    print_list(A,n);//??¨?????¨
  }
}

int main(void){
  int *A,i,n;
  
  scanf("%d",&n);
  A=(int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  insertion_sort(A,n);
  
  free(A);
  return(0);
}

Measured memory_bytes: 604
n = int(input())
a = [int(a)-1 for a in input().split()]
cnt = [0]*n
for i in a:
    cnt[i] += 1
total = 0
for i in cnt:
    total += i * (i-1) // 2
for i in a:
    print(total - (cnt[i] - 1))


Measured memory_bytes: 25764
w, h, n = map(int, input().split())
lis = []
for i in range(n):
  lis.append(list(map(int, input().split())))
x=0
y=0

for i in lis:
  if i[2] == 1:
    if x < i[0]:
      x=i[0]
  elif i[2] == 2:
    if i[0] < w:
      w=i[0]
  elif i[2] == 3:
    if y < i[1]:
      y=i[1]
  else:
    if i[1] < h:
      h=i[1]
x_a = w-x
y_a= h-y
if x_a < 0 or y_a < 0:
  print(0)
  exit()
print(x_a*y_a)

Measured memory_bytes: 3064
// 世界は変わらない
#include <bits/stdc++.h>
#define int long long int
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define ff first
#define ss second

using namespace std;

void solve()
{
    int n;
    cin >> n;
    cout << (n >= 30 ? "Yes" : "No");
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int K, X;
    cin >> K >> X;
    
    int s = max(X-K+1, -1000000);
    int e = min(X+K-1,  1000000);
    cout << s;
    for(int x=s+1; x<=e; x++) cout << " " << x;
    cout << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>

using namespace std;

const int MAX=1000;

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

int main(){
    int r0,w0,r;
    double c;
    while(cin >>r0>>w0>>c>>r && r0){
        int c_now = r0/w0;
        int cnt=0;
        while(true){
            if(c_now<c){
                cnt++;
                c_now=(r0+cnt*r)/w0;
            }else{
                break;
            }
        }
        cout << cnt<<endl;
    }
    return 0;
}

Measured memory_bytes: 3228
#include <iostream>
#include <complex>
using namespace std;
  
double cross(complex<double> A, complex<double> B){
	return (conj(A)*B).imag();
}
 
int main(){
    complex<double> V[3], P;
    while(true){
        double x, y;
        for(int i=0; i<3; i++){
            cin >> x >> y;
            V[i] = {x, y};
        }
        cin >> x >> y;
        P = {x, y};
         
        if(!cin)break;
         
        int sum = 0;
        for(int i=0; i<3; i++){
            sum += cross(V[(i+1)%3]-V[i], (P-V[i])) > 0;
        }
        cout << (sum==0 || sum==3? "YES": "NO") << endl;
    }
    return 0;
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
 
struct edge {int /*from,*/to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> PP;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
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,1,0,-1}, dy4[4] = {-1,0,1,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 mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define np next_permutation
#define pq priority_queue
#define SZ(a) int((a).size())
#define LEN(a) int((a).length())
#define MAX(a,b,c) max((a),max((b),(c)))
#define MIN(a,b,c) min((a),min((b),(c)))
#define SORT(c) sort((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 int ll

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

    printf("%d\n",n*800-(n/15)*200);
    return 0;
}

Measured memory_bytes: 256
n = int(input())
l = [int(input()) for _ in range(n)]
q = [0]*n
for i in range(n):
  q[l[i]-1] = i
a = 1
ans = 0
for i in range(1,n):
  if q[i]>q[i-1]:
    a += 1
  else:
    ans = max(ans,a)
    a = 1
print(n-max(ans,a))


Measured memory_bytes: 20916
#include "bits/stdc++.h"

using namespace std;

void solve()
{
	long N, W;
	cin >> N >> W;

	vector<long> dp(2e5, 1e18), ws(N), vs(N);

	for (long i = 0; i < N; i++)
	{
		cin >> ws[i] >> vs[i];
	}

	dp[0] = 0;

	for (int i = 0; i < N; i++)
	{
		for (int v = 2e5; v >= 0; v--)
		{
			if (v + vs[i] > 2e5) continue;
			dp[v + vs[i]] = min(dp[v + vs[i]], dp[v] + ws[i]);
		}
	}

	long ans = 0;

	for (long i = 0; i < 200000; i++)
	{
		if (dp[i] <= W) ans = max(ans, i);
	}

	cout << ans << endl;
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 1792
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<limits>
using namespace std;
//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;

//grobal
int a[2][101] = {};
int b[2][101] = {};
int INF = -1;

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

	int sum=0;
	int tmp_sum;

	for (int i = 0; i < n; i++) {
		sum = 0;
		for (int k = 0; k <= i; k++) {
			sum += a[0][k];
		}
		for (int j = i; j < n; j++) {
			sum += a[1][j];
		}
		if (sum > tmp_sum) tmp_sum = sum;
	}

	cout << tmp_sum << endl;
}



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

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

int n, y, b, t, maxb;
double r, bud, maxbud ;

int main()
{
    while(cin >> n && n)
    {
        cin >> y;
        maxb = 0;
        maxbud = 0;

        REP(n)
        {
            cin >> b >> r >> t;
            if(t == 1) bud = 1 + y * r /100;
            else
            {
                bud = 1;
                rep(j,y) bud *= (1 + r/100);
            }
            if(bud > maxbud){ maxbud = bud; maxb = b;}
        }
        cout << maxb << endl;

    }

    return 0;
}

Measured memory_bytes: 0
//
//  main.cpp
//  atcoder
//
//  Created by cfhaiteeh on 11/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char ch[4][4];
int main() {
    for(int i=1;i<=3;i++)scanf("%s",ch[i]+1);
    for(int i=1;i<=3;i++)printf("%c",ch[i][i]);
    printf("\n");
    return 0;
}


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

int main()
{
    double a,b;
    cin>>a>>b;
    int flag=0;
    for(int i=1; i<8000; i++)
    {
        int c=floor(i*0.08);
        int d=floor(i*0.1);
        //cout<<c<<" "<<d<<endl;
        if(c==a && d==b)
        {
            flag=1;
            cout<<i<<endl;
            break;
        }
    }
    if(flag==0)
    {
        cout<<-1<<endl;
    }
}


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

using namespace std;

int main() {
  long long A, B, C, X, Y, ans;
  cin >> A >> B >> C >> X >> Y;

  long long min_num = min(X, Y);
  ans = min_num * min(2 * C, A + B) + (X - min_num) * min(2 * C, A) +
        (Y - min_num) * min(2 * C, B);

  cout << ans << endl;
}


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

typedef long long ll;
const int C=1000000007;
ll n,m,ans=1;


int main()
{
	cin>>n>>m;
	if(abs(n-m)>=2)
	{
		cout<<"0";
		return 0;
	}
	for(int i=1;i<=n;i++)
		ans=ans*i%C;
	for(int i=1;i<=m;i++)
		ans=ans*i%C;
	ans=ans*(2-abs(n-m))%C;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        if 4 * h * n - N * n - N * h > 0:
            w = (N * h * n) / (4 * h * n - N * n - N * h)
            if w > 0 and w % 1 == 0:
                print(h, n, int(w))
                exit()


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

using namespace std;

const long long INF = 10000000;

int main(){
	double n,t,a;
	double h[1000],temp[1001];
	cin >> n >> t >> a;
	for (int i = 0; i < n; i++) {
	    cin >> h[i];
		temp[i] = abs(a - t + 0.006*h[i]);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
	    if (temp[ans] > temp[i])
			ans = i;
	}
	cout << ans + 1 << endl;
}


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

using namespace std;

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

    int N, A; cin >> N >> A;
    vector<int> X(N);
    int total = 0;
    for (int i = 0; i < N; ++i) {
        cin >> X[i];
        total += X[i];
        X[i] -= A;
    }

    vector<int64_t> ways(total + N * A + 1, 0);
    ways[N * A] = 1;
    for (int i = 0; i < N; ++i)
        if (X[i] < 0)
            for (int j = -X[i]; j < int(ways.size()); ++j)
                ways[j + X[i]] += ways[j];
        else 
            for (int j = ways.size() - X[i] - 1; j >= 0; --j)
                ways[j + X[i]] += ways[j];
    cout << ways[N * A] - 1 << "\n";
}

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

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

  int modulo = 0;
  rep(i, n.size()) {
    modulo = (modulo + n[i] - '0') % 9;
  }

  if (modulo == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}
/*
*/


Measured memory_bytes: 3716
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
ll a[111], b[111], p[111], aa[111], bb[111];
int main(){
    int n;
    while(cin>>n){
        ll ans=0;
        for(int i=0; i<n; ++i){
            scanf("%lld",a+i);
            scanf("%lld",b+i);
            p[i]=i;
        }
        ll x, y;
        for(int k=0; k<100; ++k){
            for(int i=0; i<n; ++i){
                x=a[i];y=b[i];
                for(int j=0; j<n; ++j){
                    if(i==j)
                        continue;
                    if((x+a[j])*(x+a[j])+(y+b[j])*(y+b[j])>x*x+y*y){
                        x+=a[j];
                        y+=b[j];
                    }
                }
                ans=max(ans, x*x+y*y);
            }
            random_shuffle(p, p+n);
            for(int i=0; i<n; ++i){
                aa[i]=a[p[i]];
                bb[i]=b[p[i]];
            }
            for(int i=0; i<n; ++i){
                a[i]=aa[i];b[i]=bb[i];
            }
        }
        ld dans=sqrt(ans);
        cout<<fixed<<setprecision(13)<<dans<<endl;
    }
  return 0;
}




Measured memory_bytes: 256
// D - Islands War

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

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

	vector<pair<int, int>> requests;

	for (int i=0; i<M; i++) {
		int l, r;
		cin >> l >> r;
		requests.push_back(make_pair(r, l));
	}

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

	int ans = 0;
	int max_r = 0;
	for (pair<int, int> req : requests) {
		int l = req.second;
		int r = req.first;
		if (r > max_r && l >= max_r) {
			ans++;
			max_r = r;
		}
	}

	cout << ans << endl;

	return 0;
}

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

int main(){
    int N;
    cin >> N;
    std::vector<int> hight(N);
    for(int i=0; i < N; i++){
        cin >> hight.at(i);
    }
    int max_mt = 0;
    int res = 0;
    for(int i=0; i < N; i++){
        if(hight.at(i) >= max_mt){
            res ++;
        }
        max_mt = max(max_mt, hight.at(i));
    }
    cout << res << endl;
    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    int h,w; cin>> h>> w;
    string s[2*h];
    for(int i=0;i<h;i++){
        string wk;
        cin>>wk;
        s[i*2]=wk;s[i*2+1]=wk;
    }
    for(int i=0; i<2*h; i++){
        cout<<s[i]<<"\n";
    }
    return 0;

}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> a(n);
	multiset<int> ms;
	rep (i, n) {
	  cin >> a[i];
	  ms.insert(a[i]);
	}
	rep (i, n) {
	  ms.erase(ms.find(a[i]));
	  auto iter = ms.rbegin();
	  cout << *iter << endl;
	  ms.insert(a[i]);
	}
    
    return 0;
}



Measured memory_bytes: 13492
/**
 * Title:
 * Url:
 */
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main() {
    ll h, w;
    cin >> h >> w;
    
    
    if(w==1) {
        cout << 1 << endl;
        return 0;
    }

    if(h==1) {
        cout << 1 << endl;
        return 0;
    }

    ll even_w = 0;
    ll odd_w = 0;
    if(w%2==0) {
        even_w = w/2;
        odd_w = w/2;
    } else {
        even_w = w/2+1;
        odd_w = w/2;
    }
    ll ans = 0;
    if(h%2==0) {
        ans = even_w * (h/2) + odd_w * (h/2);
    } else {
        ans = even_w * (h/2+1) + odd_w * (h/2);
    }
    cout << ans << endl;
    return 0;
}

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

const int MAXN = 15;
const int MAXS = 1 << 15;
const int INF = 1e9;

int N, M;
int A[MAXN][MAXN];
int C[MAXN][MAXS];
int inner[MAXS];

int dp[MAXS][MAXN];

int main() {
	scanf("%d %d", &N, &M);
	int tot = 0;
	for (int i = 0; i < M; i++) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w); u--, v--;
		A[u][v] = A[v][u] = w;
		tot += w;
	}

	// set <-> single vertex
	for (int v = 0; v < N; v++) {
		for (int m = 0; m < (1 << N); m++) {
			for (int u = 0; u < N; u++) {
				if (m & (1 << u)) {
					C[v][m] += A[v][u];
				}
			}
		}
	}

	// vertices in a set
	for (int m = 0; m < (1 << N); m++) {
		for (int u = 0; u < N; u++) {
			if (!(m & (1 << u))) continue;
			for (int v = u+1; v < N; v++) {
				if (!(m & (1 << v))) continue;
				inner[m] += A[u][v];
			}
		}
	}

	// set initial value
	for (int m = 0; m < (1 << N); m++) {
		for (int cur = 0; cur < N; cur++) {
			dp[m][cur] = -INF;
		}
	}
	dp[1][0] = 0;

	// dp
	for (int m = 1; m < (1 << N); m++) {
		for (int v = 0; v < N; v++) {
			if (dp[m][v] == -INF) continue;
			int dpv = dp[m][v];

			// 1. add a brige from v to u
			for (int u = 0; u < N; u++) {
				if (!(m & (1 << u)) && A[v][u]) {
					dp[m|(1<<u)][u] = max(dp[m|(1<<u)][u], dpv + A[u][v]);
				}
			}
	
			// 2. add incident vertices
			int comp = (1 << N) - 1 - m;
			for (int s = comp; s > 0; s = (s - 1) & comp) {
				assert(!(m&s));
				dp[m|s][v] = max(dp[m|s][v], dpv + C[v][s] + inner[s]);
			}
		}
	}

	int ans = tot - dp[(1<<N)-1][N-1];
	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  100005

void solve()
{
    ll n,m;
    cin>>n>>m;
    vi v(n);
    rep(i,0,n)cin>>v[i];
    ll lcm=v[0]/2;
    v[0]/=2;
    rep(i,1,n)
    {
        v[i]/=2;
        lcm=(lcm*v[i])/(__gcd(lcm,v[i]));
    }
    // lcm/=2;
    set<ll>s;
    rep(i,0,n)
    {
        ll x=0;
        while(v[i]%2==0)
        {
            v[i]/=2;
            x++;
        }
        s.insert(x);
    }
    ll x=m/lcm;
    ll ans=(x+1)/2;
    if(s.size()>1)
    {
        cout<<0<<endl;
        return;
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3876
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,D = MI()
    M = 2*D + 1
    print(ceil(N/M))
if __name__ == '__main__':
    main()

Measured memory_bytes: 38512
N=int(input())
if N==1:
    print("Yes")
    print(2)
    print(1,1)
    print(1,1)
    exit()
K=-1
for i in range(1,N+1):
    if i*(i-1)==2*N:
        K=i
        break
if K==-1:
    print("No")
    exit()
else:
    print("Yes")
print(K)
L=[[] for i in range(K)]
t=1
X=[[0 for i in range(K-1)] for i in range(K)]
for i in range(K):
    for j in range(i):
        L[i].append(L[j][-1])
        L[j].pop()
    for j in range(K-1-i):
        L[i].append(t)
        t+=1
    for j in range(K-1):
        X[i][j]=L[i][j]
for i in range(K):
    S=str(K-1)
    for j in range(K-1):
        S=S+" "+str(X[i][j])
    print(S)


Measured memory_bytes: 10604
#include <stdio.h>
#define buf 200

int main(void) {
	int a,b;
	int sum,cnt;
	char str[buf];

	for( ;fgets(str,sizeof(str),stdin); ){
   		sscanf(str,"%d %d",&a,&b);
		cnt=0;
		for(sum=a+b;sum>0;sum/=10)
			cnt++;
		printf("%d\n",cnt);
	}
	return 0;
}

Measured memory_bytes: 608
#include <iostream>
#include <string>
using namespace std;
int main(){
  long long N,O,c=0;
  string S;
  char t=0;
  cin>>N;
  cin>>S;
  O=N;
  for(long long i=0;i<N;i++){
    if(t!=S[i]){
      O-=c;
      c=0;
      t=S[i];
    }else{
      c+=1;
    }
    if(i==N-1&&c!=0)O-=c;
  }
  cout<<O<<endl;
}

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

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)

inline unsigned long long get_cycle() {
  unsigned int low, high;
  __asm__ volatile("rdtsc" : "=a"(low), "=d"(high));
	return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}

constexpr double one_clock = 0.00000035714;
class Timer {
  public:
	unsigned long long start_time;
	Timer() {
		start_time = get_cycle();
	}
	inline int get_time() {
		return get_cycle() * one_clock - start_time * one_clock;
	}
};

class Rand_int {
  public:
	int x = 8753, y = 239017, z = 1000000123;
	inline int next(int i) {
		int t = x ^ (x << 11);
		x = y;
		y = z;
		z ^= (z >> 19) ^ t ^ (t >> 8);
		return z % i;
	}
};

using Pi=pair<int,int>;
using ll=long long;

Timer timer;
Rand_int ri;

int N;
vector<Pi> p;

struct State{
	bitset<100> ans;
	ll nx,ny,last_i;
	ll score,last_score;
	State(){
		nx=ny=score=last_score=0;
	}
	void modify(){
		int i=ri.next(N);
		last_i=i,last_score=score;
		if(ans[i]){
			nx-=p[i].first;
			ny-=p[i].second;
		}else{
			nx+=p[i].first;
			ny+=p[i].second;
		}
		ans[i]=~ans[i];
	}
	void cancel(){
		int i=last_i;
		score=last_score;
		if(ans[i]){
			nx-=p[i].first;
			ny-=p[i].second;
		}else{
			nx+=p[i].first;
			ny+=p[i].second;
		}
		ans[i]=~ans[i];
	}
	void set_score(){
		score=nx*nx+ny*ny;
	}
	void print_answer(){
		printf("%.16f\n",sqrt((ll)score));
	}
};

int main() {
	cin>>N;
	p.resize(N);
	FOR(i,N){
		cin>>p[i].first>>p[i].second;
	}
	State state,best_state;
	best_state=state;int t,c=0;
	while((t=timer.get_time())<1900){
		state.modify();
		state.set_score();
		//state.print();cerr<<state.score<<endl;
		if(best_state.score<state.score){
			best_state=state;
		}
		if(state.score<state.last_score){
			double rate=(state.last_score-state.score)/(double)max(1LL,(state.last_score));
			//cerr<<rate<<endl;
			if(rate*1000>ri.next((1900-t)*1000/1900+1)){
				state.cancel();
			}else{
				cerr<<"accept! "<<rate<<endl;
			}
		}
		//cerr<<best_state.score<<endl;
		c++;
	}
	best_state.print_answer();
  return 0;
}


Measured memory_bytes: 256