akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {

    public static void main(String args []) {

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        long[] list = new long[n];
        long sum = 0;
        long mod = 1000000007;
        long ans = 0;

        for (int i = 0; i<n; i++) {
            long a = scan.nextLong();
            list[i] = a;
            sum += a;
            sum %= mod;

        }

        for (int i = 0; i<n; i++) {

            sum= sum - list[i];
            if (sum < 0)  {
                sum += mod;
            }

            ans += list[i] * sum;
            ans %= mod;
        }

        System.out.println(ans);

    }
}


Measured memory_bytes: 60596
#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair 
#define f(i,n) for(int i=0;i<n;i++) 
#define F first 
#define S second 
#define pb push_back 

using namespace std;

ll cache[100005];

ll dp(ll a[],ll n,ll k){
	if(n<=0)
		return 0;
	if(n==1)
		return abs(a[1]-a[0]);
	if(cache[n]!=-1)
		return cache[n];
	ll &ans = cache[n];
	
	ans = abs(a[n]-a[n-1]) + dp(a,n-1,k);
	
	for(int i=1;i<=k;i++){
		if(n-i>=0)
			ans = min(ans,abs(a[n]-a[n-i]) + dp(a,n-i,k));
	}
	return ans;
	
}

void test(){
	ll n,k;
	cin>>n>>k;
	ll a[n];
	f(i,n)cin>>a[i];
	reverse(a,a+n);
	
	memset(cache,-1,sizeof(cache));
	
	cout<<dp(a,n-1,k);
	
	
}

int main(){
	int tests=1;
	// cin>>tests;
	while(tests--){
		test();
	}
}


Measured memory_bytes: 12996
N = int(input())
li = [ int(it) for it in input().split() ]
import collections as col
cc = col.Counter(li)
go = []
x = 0
s = 0
for k,v in cc.items():
  go.append( [k,v] )
  s += 1
  if ( v>1 ):
    x += v-1
if ( x%2 == 0 ):
  print (s)
else:
  print (s-1)

Measured memory_bytes: 64168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, m;

const int Z = 100;

int me[Z][Z];
int D[11][11];

int main()
{
	read(n, m);
	
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
		int d; read(d);
		D[i][j]=d;
		for(int a=0; a<=Z-1; ++a) for(int b=0; b<=Z-1; ++b){
			me[a][b] = max(me[a][b], d - i*a - j*b);
		}
	}
	
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
		int cd = 1e9;
		for(int a=0; a<=Z-1; ++a) for(int b=0; b<=Z-1; ++b){
			cd = min(cd, me[a][b] + i*a + j*b);
		}
		if(cd != D[i][j]){
			puts("Impossible");
			return 0;
		}
	}
	puts("Possible");
	printf("%d %d\n", Z*2, Z*Z + (Z-1)*2);
	for(int i=2; i<=Z; ++i) printf("%d %d X\n", i-1, i);
	for(int i=Z+1; i<Z*2; ++i) printf("%d %d Y\n", i+1, i);
	for(int a=0; a<=Z-1; ++a) for(int b=0; b<=Z-1; ++b){
		printf("%d %d %d\n", 1+a, Z+1+b, me[a][b]);
	}
	printf("%d %d\n", 1, Z+1);
	return 0;
}


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, pos1 = -1;
    cin >> n >> k;

    if(n <= k)
        return cout << 1 << '\n', 0;

    for(int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;

        if(x == 1)
            pos1 = i;
    }

    int answer = 1e9;

    for(int i = 1; i <= k; ++i)
    {
        int temp_ans = 1;
        int beg = pos1 - i, en = n - k - beg;

        if(beg > 0)
            temp_ans += (pos1 - i) / (k - 1) + (bool)((pos1 - i) % (k - 1));

        if (en > 0)
            temp_ans += en / (k - 1) + (bool)(en % (k - 1));

        //cout << i << ' ' << temp_ans << '\n';
        answer = min(answer, temp_ans);
    }

    cout << answer << '\n';

}


Measured memory_bytes: 256
/*
 *
 */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>


using namespace std;

int times[56] = { 0,
	      1,
	      1, 2,
	      2, 2, 3,
	      3, 3, 3, 4,
	      4, 4, 4, 4, 5,
	      5, 5, 5, 5, 5, 6,
	      6, 6, 6, 6, 6, 6, 7,
	      7, 7, 7, 7, 7, 7, 7, 8,
	      8, 8, 8, 8, 8, 8, 8, 8, 9,
	      9, 9, 9, 9, 9, 9, 9, 9, 9, 10
};

int main(void) {
  long long n;

  while (cin >> n) {
    if (n == 1) {
      cout << 0 << endl;
      continue;
    }

    long long f = 2;
    long long max_loop = 1e6;

    int total = 0;
    int acc = 0;
    
    while (n != 1) {
      if (n % f == 0) {
	acc++;
	n /= f;
      } else {
	total += times[acc];
	acc = 0;
	f += 1;

	if (f > sqrt((double)n)) {
	  acc++;
	  break;
	}
      }
    }
    
    total += times[acc];

    cout << total << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3680
#include<iostream>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long 
using namespace std;
int main(){
  ll h; cin >>h;
  rep(i,40){
    if((ll)pow(2,i)<=h&&h<(ll)pow(2,i+1)){
      cout <<(ll)pow(2,i+1)-1<<endl;
      break;
    }
  }
}

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

int main(){
    long long N, M, K;
    std::cin >> N >> M >> K;
    std::vector< long long > A(N);
    std::vector< long long > B(M);
    for(long long i=0; i<N; i++){
        std::cin >> A[i];
    }
    for(long long i=0; i<M; i++){
        std::cin >> B[i];
    }
    
    long long a_ind = 0;
    long long time = 0;
    while(a_ind != N && time + A[a_ind] <= K){
        time += A[a_ind];
        a_ind++;
    }
    
    long long b_ind = 0;
    while(b_ind != M && time + B[b_ind] <= K){
        time += B[b_ind];
        b_ind++;
    }
    
    long long max = a_ind + b_ind;
        
    for(long long i=a_ind-1; i >= 0; i--){
        time -= A[i];
        while(b_ind != M && time + B[b_ind] <= K){
            time += B[b_ind];
            b_ind++;
        }
        
        if(max < i + b_ind){
            max = i + b_ind;
        }
    }
    
    std::cout << max << std::endl;
    
    return 0;
}



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

int main(){
  int n;
  cin >> n;
  vector<int> d(n);
  for(int i=0; i<n; i++){
    cin >> d[i];
  }
  
  sort(d.begin(), d.end());
  
  int ans = d[d.size()/2] - d[d.size()/2 - 1];
  
  cout << ans << endl;
}

Measured memory_bytes: 640
class CircleInRectangle
	def contain_circle? (val_array)
		w = val_array[0]
		h = val_array[1]
		x = val_array[2]
		y = val_array[3]
		r = val_array[4]
		x_range = ((x >= r) && (x <= w-r))
		y_range = ((y >= r) && (y <= h-r))

		puts (x_range && y_range) ? "Yes" : "No"
	end
end

input = gets.split.map(&:to_i)
CircleInRectangle.new.contain_circle?(input)

Measured memory_bytes: 6104
#include<iostream>
#include<math.h>
#include<iomanip>

int main() {
	int R;
	std::cin >> R;

	const double pi = acos(-1.0);

	double ans = 2.0 * R * pi;
	std::cout << std::setprecision(20) << std::fixed << ans << std::endl;
	return 0;
}

Measured memory_bytes: 3784
#include<bits/stdc++.h>
#define ll long long int
#define ss second
#define ff first
#define Mem(x,val) memset(x,val,sizeof x)
#define pb push_back
#define all(v) v.begin(),v.end()
#define unik(v)  v.erase(unique(v.begin(),v.end()),v.end())
#define cerr(x) cerr << __LINE__ << " th Line : " << #x << " = " << x << "\n"
#define debug(a,b) cerr << #a<<" = "<<a<<"   |   "<<#b<<" = "<<b<<'\n'
#define endl '\n'
#define SZ(a) ((int)a.size())
using namespace std;
typedef pair<int, int> pi32;
typedef pair<ll, ll> pi64;
typedef vector<int> vi32;
typedef vector<ll> vi64;
typedef vector<pi32> vp32;
typedef vector<pi64> vp64;
const ll mod = 1e9 + 7;
const int MX = 1e5+7;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int k;cin>>k;
	string s;cin>>s;
	if(SZ(s)<=k)cout<<s<<endl;
	else{
		for(int i=0;i<k;i++)cout<<s[i];
		cout<<"...\n";
	}
	return 0;
}


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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int MOD2 = MOD + 2; //1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

int main() 
{
    int n;
    cin>>n;
    vi a(n+1);
    vi b(n+1,0);
    FOR(i,1,n+1)
    {
      cin>>a[i];
      b[a[i]]++;
    }
    FOR(i,1,n+1)
    {
      cout<<b[i]<<endl;
    }
  return 0;
}

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

int n;
double dp[302][302][302];
double solve(int a, int b, int c) {
    if(a==0 && b==0 && c==0)
        return 0;
    if(dp[a][b][c]!=0)
        return dp[a][b][c];
    int s = a+b+c;
    double ans = 0;
    if(a>0)
        ans+=a*(solve(a-1, b, c))/s;
    if(b>0)
        ans+=b*(solve(a+1, b-1 ,c))/s;
    if(c>0)
        ans+=c*(solve(a, b+1, c-1))/s;
    return dp[a][b][c]=ans+ (n)/(double)s ;
}
int m[4];
int main() {
    cin>>n;
    int i;
    for(i=1;i<=n;i++) {
        int x;
        cin>>x;
        m[x]++;
    }
	cout<<setprecision(20)<<solve(m[1],m[2],m[3]);
	return 0;
}

Measured memory_bytes: 215296
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;cin>>N>>M;
    vector<long> X(M),D(M-1);
    for(int i=0;i<M;i++){
        cin>>X[i];
    }sort(X.begin(),X.end());
    for(int j=0;j<=M-2;j++){
        D[j]=X[j+1]-X[j];
    }sort(D.begin(),D.end());
    if(N>=M){
        cout<<0<<endl;
    }else{
        long result=0;
        for(int k=0;k<M-N;k++){
            result+=D[k];
        }cout<<result<<endl;
    }
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mem(arr,v) memset(arr,v,sizeof(arr))
/*bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
} */
int main()
{
     string str;
     ll arr[26],cnt=0;
     mem(arr,0);
     cin>>str;
     for(int i=0;i<str.size();i++)
     {
         arr[str[i]-'a']++;
     }
     for(int i=0;i<26;i++)
     {
         if(arr[i]%2!=0)
         {
             cout<<"No"<<endl,cnt=10;
             return 0;
         }
     }
     if(cnt==0)
        cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	long long a,b,u=0,v;
	scanf("%d%lld%lld",&n,&a,&b);
	for (int i=2;i<n;i++)
	{
		long long x;
		scanf("%lld",&x);
		u^=x;
	}
	if ((a+b)%2!=u%2 || a+b<u)
	{
		printf("-1");
		return 0;
	}
	v=(a+b-u)/2;
	if (u&v)
	{
		printf("-1");
		return 0;
	}
	long long ans=0;
	for (int i=0;i<50;i++)
	{
		if (!(u&(1LL<<i)))
		ans|=(v&(1LL<<i));
	}
	if (ans>a)
	{
		printf("-1");
		return 0;
	}
	for (int i=49;i>=0;i--)
	{
		if (u&(1LL<<i) && (ans|(1LL<<i))<=a)
		ans|=(1LL<<i);
	}
	if (!ans)
	{
		printf("-1");
		return 0;
	}
	printf("%lld",a-ans);
}

Measured memory_bytes: 3824
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);

        for(int i = 0; i < n; i++){
            q.add(sc.nextInt());
        }
        long ans = 0;

        LinkedList<Integer> pos = new LinkedList<>();

        pos.add(q.poll());

        while(!q.isEmpty()){
            ans += pos.poll();
            int a = q.poll();
            pos.add(a);
            pos.add(a);
        }

        System.out.println(ans);

    }
}


Measured memory_bytes: 68072
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

A1 = 0
A2 = 0
index = -1
for i in range(N):
    if A1 == 0:
        A1 = max(A1,A[i])
        index = i
    else:
        tmp = max(A2,A[i])
        if A1 <= A[i]:
            A2 = A1
            A1 = A[i]
            index = i
        elif A2 <= tmp:
            A2 = tmp

if A1 == A2:
    for i in range(N):
        print(A1)
else:
    for i in range(N):
        if i == index:
            print(A2)
        else:
            print(A1)

Measured memory_bytes: 69452
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import defaultdict, deque
    N = int(input())
    G = [[] for i in range(N)]
    cost = defaultdict(int)
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cost[a-1, b-1] = c
        cost[b-1, a-1] = c
    Q, K = (int(i) for i in input().split())
    dist = [-1 for _ in range(len(G))]

    def bfs(s):
        que = deque()
        dist[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + cost[v, u]
                que.append(v)

    bfs(K-1)
    for q in range(Q):
        x, y = (int(i)-1 for i in input().split())
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()


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

int main() {
    // your code goes here
    ll h, k = 1, sum = 0;
    cin >> h;
    while(h) {
        sum += k;
        k *= 2;
        h /= 2;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque
inf=10**6
dx=[-1,0,1,0]
dy=[0,1,0,-1]
h,w=map(int,input().split())
maze=[list(input()) for _ in range(h)]
def bfs(sx,sy):
    dist=[[inf for _ in range(w)] for _ in range(h)]
    dist[sx][sy]=0
    d=deque()
    d.append([sx,sy])
    while d:
        x,y=d.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or nx>=h or ny<0 or ny>=w or maze[nx][ny]=='#' or dist[nx][ny]!=inf:
                continue
            d.append([nx,ny])
            dist[nx][ny]=dist[x][y]+1
    val=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]!=inf:
                val=max(val,dist[i][j])
    return val
ans=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            ans=max(ans,bfs(i,j))
print(ans)


Measured memory_bytes: 3316
# import random

import numpy as np
n = int(input())
a = list(map(int,input().split()))
a = np.array(a)
q = int(input())
# a = [random.randint(0, 10**4) for i in range(10**4)]
# 処理前の時刻
# t1 = time.time() 
import collections
co = collections.Counter(a)
s = 0
for k,v in co.items():
    s+=k*v
for i in range(q):
    b,c = map(int,input().split())
    if b in co.keys():
        s += (c-b)*co[b]
        co[c]+=co[b]
        co.pop(b)
    print(s)

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

/*struct Benri {
    Benri() {
        std::cin.tie(0); ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
    }
} benri;*/
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; }

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define MOD 1000000007
#define MOD2 998244353
const int INF = 1 << 28;


int main() {
    int N; cin >> N;
    vll A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];

    priority_queue<pair<ll, int>> pq;
    rep(i, N) pq.push(mp(B[i], i));

    bool can = true;
    ll ans = 0;

    while (!pq.empty()) {
        ll C = pq.top().F;
        int i = pq.top().S;
        pq.pop();
        ll X = B[(i - 1 + N) % N] + B[(i + 1) % N];

        if (C < A[i]) {
            can = false;
            break;
        }
        else if (C == A[i]) {
            continue;
        }
        else if (C > A[i] && C < X + A[i]) {
            can = false;
            break;
        }
        else {
            ll tmp = (C - A[i]) / X;
            C = C - X * tmp;
            B[i] = C;
            ans += tmp;
            pq.push(mp(C, i));
        }
    }

    cout << (can ? ans : -1) << endl;

}




Measured memory_bytes: 9456
#include <iostream>
#include <algorithm>
#define MAX_V 100
#define MAX_N 1000
#define INF 9999999
using namespace std;

int d[MAX_V][MAX_V];
int a[MAX_N],b[MAX_N],c[MAX_N];

int N,M;

void input(){
    cin >> N >> M;
    for(int i = 0; i < M;++i){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
    }
    for(int i = 0; i < N; ++i){
        for(int j = 0;  j < N; ++j){
            if(i == j)d[i][j] = 0;
            else d[i][j] = INF;
        }
    }
}

void warshall_floyd(){
    for(int k = 0; k < N; ++k){
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
               d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main(){
    input();

    for(int i = 0; i < M; ++i){
        d[a[i]][b[i]] = min(d[a[i]][b[i]],c[i]);
        d[b[i]][a[i]] = min(d[b[i]][a[i]],c[i]);
    }

    warshall_floyd();//ワーシャルフロイド法を用いて全ての頂点同士の最短距離を計算させている。

    int ans = M;//初期の辺の数
    bool is_shortest = false;
    for(int i = 0; i < M; ++i){
        is_shortest = false;
        for(int j = 0; j < N; ++j){
            if(d[j][a[i]] + c[i] == d[j][b[i]]){ 
                is_shortest = true;//最短距離で使っている辺である。
            }
        }
        if(is_shortest==true) ans--;//最短距離で使っている辺だったので減らす。
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
function Main(input) {
	const data = input.trim().split("\n");
  	const n = Number(data[0]);
  	const sps = data.slice(1).map(d => d.split(" "));
  	const sortedSps = sps.slice();
  	sortedSps.sort((a, b) => {
    	if (a[0] < b[0]) {
          return -1;
        } else if (b[0] < a[0]) {
          return 1;
        } else {
          if (Number(a[1]) < Number(b[1])) {
            return 1;
          } else {
            return -1;
          }
        }
    });
  	const result = [];
  	for (let i = 0; i < sps.length; i++) {
      const index = sps.findIndex(sp => sp[0] === sortedSps[i][0] && sp[1] === sortedSps[i][1]);
      result.push(index + 1);
    }
    console.log(result.join("\n").trim());
  	
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7628
#include "bits/stdc++.h"
using namespace std;
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define pb push_back
#define nl cout<<"\n"
#define endl "\n"
#define ll long long
#define ld long double
#define all(c) (c).begin(),(c).end()
#define trav(a,x) for(auto a = x.begin() ; a != x.end() ; a++)
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define f first
#define s second

inline ll max(ll a,ll b) {return ((a>b)?a:b);}
inline ll min(ll a,ll b) {return ((a>b)?b:a);}
inline ll gcd(ll a ,ll b) {if(b==0) return a; a%=b;return gcd(b,a);}
ll power(ll x, ll y){if(y == 0) return 1; ll a = power(x,y/2);if (y % 2 == 0) return a * a; else return x * a * a; }
ll powermod(ll x, ll ex , ll md) {ll ans = 1ll;while (ex > 0) {if (ex & 1ll) ans = (ans * x) % md; ex >>= 1ll;x = (x * x) % md;}return ans;}

const ll inf = 1e18 + 9;
const ll mod = 1e9 + 7;
const ld PI = acos(-1);
const ld eps = 1e-9;

const ll N = 1e6 + 1;

void solve(){
    ll n , k;
    cin >> n >> k;
    ll a[n];
    rep(i , n ) cin >> a[i];
    sort(a , a + n);
    ll s =0 ;
    for(ll i =0 ; i < k ; i++) s +=a[i];
    cout << s << endl;
}
int main(){
    IOS;
    cout << fixed << setprecision(20);
    ll NTC=1;
    // cin>>NTC;
    ll PTC=0;
    while(PTC++<NTC){
        // cout<<"Case #"<<PTC<<":"<<' ';
        solve();
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


Measured memory_bytes: 3800
d=[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000]
def f(input):
    h = 1
    for i in d:
        if input >= i:
            h = i
        else:
            print(h)
            return 0
    print(1000)
if __name__=='__main__':
    input=int(input())
    f(input)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int,int> a[100005];
int n,m,x=1e9;
int main(){
	cin >> n >> m;
	for(int i=0;i<m;i++)
		cin >> a[i].first >> a[i].second;
	sort(a,a+m);
	for(int i=0;i<m;i++)
		x=min(x,a[i].second);
	cout << max(x-a[m-1].first+1,0);
    return 0;
}

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

using namespace std;
long long dig[10];
int main()
{
    //freopen("cbarn.out", "w", stdout) ;
    //freopen("cbarn.in", "r", stdin) ;
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(0);
    long long a,b,pos,num;
    bool bruh=false,ag[10];
    cin>>a>>b;
    set <int> h;
    for(int i=0;i<b;i++)
    {
        cin>>pos>>num;
        if(h.count(pos)==0||dig[pos-1]==num)
        {
            dig[pos-1]=num;
        }
        else
        {
            bruh=true;
        }
        h.insert(pos);
    }
    if(bruh==true)
        {cout<<"-1"; return 0;}
    if(a==1)
    {cout<<dig[0]; return 0;}
        if(h.count(1)==0)
        {
            cout<<"1";
            for(int i=1;i<a;i++)
                cout<<dig[i];
        }
        else
        {
            if(dig[0]==0)
                cout<<"-1";
            else
            {
                for(int i=0;i<a;i++)
                    cout<<dig[i];
            }
        }
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m;
char flag[55][55];

int cnt(int a, int b, int c){
	int ret = 0;
	for (int i = 0;i < n;i++){
		for (int j = 0;j < m;j++){
			if(i < a){ if(flag[i][j] != 'W') ret++;}
			else if(i < b){ if( flag[i][j] != 'B') ret++;}
			else if(i < c){ if( flag[i][j] != 'R') ret++;}
		}
	}
	return ret;
}

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

	cin >> n >> m;

	for (int i = 0;i < n;i++){
		for (int j = 0;j < m;j++){
			cin >> flag[i][j];
		}
	}

	int ans = INT_MAX;

	for (int i = 1;i < n;i++){
		for (int j = 1;j < n-i;j++){
			ans = min(ans,cnt(i,i+j,n));
		}
	}

	cout << ans << endl;

	return 0;

}



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

int main(){
  int n;
  cin>>n;
  int num[8]={400,800,1200,1600,2000,2400,2800,3200};
  vector<bool> flag(8,false);
  int count=0;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    if(x<num[0]) flag[0]=true;
    else if(x<num[1]) flag[1]=true;
    else if(x<num[2]) flag[2]=true;
    else if(x<num[3]) flag[3]=true;
    else if(x<num[4]) flag[4]=true;
    else if(x<num[5]) flag[5]=true;
    else if(x<num[6]) flag[6]=true;
    else if(x<num[7]) flag[7]=true;
    else count++;
  }int ans=0;
  for(int i=0;i<8;i++){
    if(flag[i]) ans++;
  }if(ans==0&&count!=0){
    cout<<1<<' '<<count<<endl;
    return 0;
  }
  cout<<ans<<' ';
  cout<<ans+count;
  cout<<endl;
}

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

int main() {
  int h,w;
  cin >> h >> w;
  vector<string> v(h);
  rep(i,h) cin >> v[i];
  int ans=0;
  rep(i,h)rep(j,w){
      if(v[i][j]=='#') continue;
      queue<P> q;
      q.push(make_pair(i,j));
      vector<vector<int>> vec(h,vector<int>(w,-1));
      vec[i][j]=0;
      while(!q.empty()){
          P now=q.front(); q.pop();
          int x=now.first,y=now.second;
          if(x!=0)if(v[x-1][y]=='.'&&vec[x-1][y]==-1){
              q.push(make_pair(x-1,y));
              vec[x-1][y]=vec[x][y]+1;
              ans=max(ans,vec[x][y]+1);
          }
          if(x!=h-1)if(v[x+1][y]=='.'&&vec[x+1][y]==-1){
              q.push(make_pair(x+1,y));
              vec[x+1][y]=vec[x][y]+1;
              ans=max(ans,vec[x][y]+1);
          }
          if(y!=0)if(v[x][y-1]=='.'&&vec[x][y-1]==-1){
              q.push(make_pair(x,y-1));
              vec[x][y-1]=vec[x][y]+1;
              ans=max(ans,vec[x][y]+1);
          }
          if(y!=w-1)if(v[x][y+1]=='.'&&vec[x][y+1]==-1){
              q.push(make_pair(x,y+1));
              vec[x][y+1]=vec[x][y]+1;
              ans=max(ans,vec[x][y]+1);
          }
      }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3616
from itertools import groupby
S = input()
K = int(input())
A = list(map(lambda x: (x[0], len(list(x[1]))), groupby(S)))
a1 = A[0]
a2 = A[-1]
if len(A) == 1:
    print(len(S) * K // 2)
elif a1[0] != a2[0]:
    print(K * sum(x // 2 for _, x in A))
else:
    print(K * sum(x // 2 for _, x in A) - (K - 1) * (a1[1] // 2 + a2[1] // 2 - (a1[1] + a2[1]) // 2))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int main(void) {
    while(~scanf("%d%d%d", &n, &m, &k)) {
        bool flag = false;
        for(int i = 0; i <= n && !flag; ++i) {
            for(int j = 0; j <= m && !flag; ++j) {
                if(i * (m - j) + j * (n - i) == k) flag = true;
            }
        }
        puts(flag ? "Yes" : "No");
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll n, c[5] = {};
string s;

int main() {
	cin >> n;
	rep(i, n) {
		cin >> s;
		if (s == "AC")c[0]++;
		if (s == "WA")c[1]++;
		if (s == "TLE")c[2]++;
		if (s == "RE")c[3]++;
	}
	cout << "AC x " << c[0] << endl;
	cout << "WA x " << c[1] << endl;
	cout << "TLE x " << c[2] << endl;
	cout << "RE x " << c[3] << endl;
	return 0;
}

Measured memory_bytes: 3632
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
using namespace std;

int main()
{
    fast_io
    ll i,j,n,diff;
    string s;
    cin>>n>>i;
    diff=abs(1-i);
    return cout <<n-diff<<endl,0;
    return 0;
}





Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int n = 2e5 + 5;
const ll INF = 1.5e18;

int N, K;
int P[n], inc[n];
bool vis[n], vis2[n], pos[n];
bool in[n];

bool hasInv(int x){
	return inc[min(N-1, x+K-1)] - inc[x] > 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N >> K;
	for(int i = 0; i < N; ++i){
		cin >> P[i];
		if(i >= 1){
			in[i] = P[i] < P[i-1];
			inc[i] = inc[i-1] + in[i];
		}
	}
	/*
	for(int i = 0; i < N; ++i){
		cout << in[i];
	}
	cout << endl;
	for(int i = 0; i < N; ++i){
		cout << inc[i];
	}
	cout << endl;
	for(int i = 0; i < N-K+1; ++i){
		cout << hasInv(i);
	}
	cout << endl;
*/
	//P[N] = N;
	//N++;
	priority_queue<int,vector<int>, greater<int>> Q;
	priority_queue<int> QX;
	for(int i = 0; i < K; ++i){
		Q.push(P[i]);
		QX.push(P[i]);
	}
	int c = 1;
	int noIC = !hasInv(0);
	for(int i = K; i < N; ++i){
		vis[P[i-K]] = true;
		bool p = (P[i-K] != Q.top() || P[i] <= QX.top());
		while(!Q.empty() && vis[Q.top()])
			Q.pop();
		while(!QX.empty() && vis[QX.top()])
			QX.pop();
		Q.push(P[i]);
		QX.push(P[i]);
		//int s = Q.size();
		c += p;
		if(p)
			noIC += !hasInv(i-K+1);
	}
	if(noIC >= 2)
		c -= noIC-1;
	cout << c << endl;
	return 0;
}


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

// N 個の要素を含む 0-オリジンの配列 A
int selectionSort(vector<int> &A, int N) {
  int minj;
  int count = 0;

  for (int i = 0; i < N; i++) {
    minj = i;

    for (int j = i; j < N; j++) {
      if (A.at(j) < A.at(minj)) {
        minj = j;
      }
    }

    if (i != minj) {
      swap(A.at(i), A.at(minj));
      count++;
    }
  }

  return count;
}

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

  vector<int> A(N);

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

  int count = selectionSort(A, N);

  for (int i = 0; i < N; i++) {
    if (i != N - 1) {
      cout << A.at(i) << " ";
    } else {
      cout << A.at(i) << endl;
    }
  }

  cout << count << endl;
}



Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[32]={1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51};
    int k;
    cin>>k;
    cout<<a[k-1]<<endl;
}





Measured memory_bytes: 3572
S = input()
ans = 'Yes'
for i, si in enumerate(S):
    if (i + 1) % 2 == 1:
        if si not in ['R', 'U', 'D']:
            ans = 'No'
    else:
        if si not in ['L', 'U', 'D']:
            ans = 'No'

print(ans)


Measured memory_bytes: 2940
N=int(input())
P=list(map(int, input().split()))

cnt=1

if N==1:
    print(1)
elif N==2:
    if P[1] < P[0]:
        print(2)
    else:
        print(1)
else:
    tmp = P[0]
    if P[1] <= P[0]:
        cnt +=1
    for i in range(2,N):
        tmp = min(P[i-1],tmp)
        if P[i] <= tmp:
            cnt+=1
    print(cnt)

Measured memory_bytes: 32296
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)
const ll mod=1e9+7;

int main(){
   ll n;
   string s;
   cin >> n;
   map<int,int> cnt;
   rep(i,n){
      int x;
      cin >> x;
      cnt[x]++;
   }
   ll ans=1LL;
   bool f=true;
   if (n%2==1){
      if (cnt[0]!= 1) f=false;
      for (int i = 0;i < n/2;i++){
         int id=2;
         if (cnt[id]!=2) {
            f=false;
            break;
         }
         id+=2;
         ans*=2;
         ans%=mod;
      }
   }
   else{
      for (int i =0;i < n/2;i++){
         int id=1;
         if (cnt[id]!=2) {
            f=false;
            break;
         }
         id+=2;
         ans*=2;
         ans%=mod;
      }
   }
   if (f) cout << ans << endl;
   else cout << 0 << endl;
   
   return 0;
}



Measured memory_bytes: 3200
import functools
t = int(input())

@functools.lru_cache(maxsize=None)
def tk(v,a,b,c,d):
    if v == 0:
        return 9999999999
    elif v == 1:
        return d

    pas1 = v // 2
    if v == 2 :
        pas2 = 0  #無限ループ阻止のため
    else:
        pas2 = pas1 + 1 # vが2の時無限ループになる
    pam1 =  v % 2 
    pam2 = 2 - pam1
    pbs1 = v // 3
    pbs2 = pbs1 + 1
    pbm1 = v % 3 
    pbm2 = 3 -pbm1  
    pcs1 = v // 5
    pcs2 = pcs1 +  1
    pcm1 = v % 5 
    pcm2 = 5 - pcm1

    koho_a1 = tk(pas1,a,b,c,d) + pam1*d + a
    koho_b1 = tk(pbs1,a,b,c,d) + pbm1*d + b
    koho_c1 = tk(pcs1,a,b,c,d) + pcm1*d + c
    koho_a2 = tk(pas2,a,b,c,d) + pam2*d + a
    koho_b2 = tk(pbs2,a,b,c,d) + pbm2*d + b
    koho_c2 = tk(pcs2,a,b,c,d) + pcm2*d + c
    
    ret = min(v*d,koho_a1,koho_a2,koho_b1,koho_b2,koho_c1,koho_c2 ) 
    return ret

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    print(tk(n,a,b,c,d))
    tk.cache_clear()


Measured memory_bytes: 129648
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
const int N = 3e5+5;
vector<int>v[N];
void solve(){
	int n; 
	cin>>n; 
	for(int i=2;i<=n;i++){
		int x; 
		cin>>x; 
		v[x].pb(i);
	}
	for(int i=1;i<=n;i++)cout<<v[i].size()<<endl;
	
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}


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

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int x, a; cin >> x >> a;
  cout << (x < a ? 0 : 10) << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		if (n % 2 == 0) {
			System.out.println(n / 2);
		} else {
			System.out.println(n / 2 + 1);
		}

	}

}


Measured memory_bytes: 21716
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e8
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main(void) {
    int i,j,k;
    int n,m,s,g1,g2;
    int v[100][100];
    while(cin >> n >> m >> s >> g1 >> g2, n){
        s--;g1--;g2--;
        rep(i,n)rep(j,n){
            if(i == j) v[i][j] = 0;
            else v[i][j] = INF;
        }
        rep(i,m){
            int a,b,c;
            cin >> a >> b >> c;
            a--;b--;
            v[a][b] = c;
        }
        rep(k,n)rep(i,n)rep(j,n){
            v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
        }
        int ans = INF;

        rep(i,n){
            if(v[s][i] < INF && v[i][g1] < INF && v[i][g2] < INF){
                //cout << i << " " << v[s][i] + v[i][g1] + v[i][g2] << endl;
                if(ans > v[s][i] + v[i][g1] + v[i][g2]){
                    ans = v[s][i] + v[i][g1] + v[i][g2];
                    //cout << i << " " << ans << endl;
                }
            }
        }
        cout << ans << endl;
    }
}



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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a, b) accumulate(all(a), b)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
ll const INF = 1e18;

template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int a, p;
    cin >> a >> p;
    cout << (3*a + p) / 2 << endl;
    return 0;
}


Measured memory_bytes: 764
import * as fs from 'fs';

namespace AtCoder.abc131 {
    class ProgramB {
        args: string[];

        constructor(args: string[]) {
            this.args = args;
        }

        main(this: ProgramB) {
            const [n, l]: number[] = this.args[0].split(' ').map(Number);

            let sum: number = 0;
            let moreSmall: number = Infinity;
            for (let i = 1; i <= n; i++) {
                sum += l + i - 1;
                if (Math.abs(moreSmall) > Math.abs(l + i - 1)) {
                    moreSmall = l + i - 1;
                }
            }

            if (sum >= 0 && moreSmall >= 0 || sum < 0 && moreSmall < 0) {
                console.log(sum - moreSmall);
            } else {
                console.log(sum + moreSmall);
            }
        }
    }

    new ProgramB(fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n')).main();
}


Measured memory_bytes: 7372
import java.util.*;class Main{public static void main(String[]args){Scanner sc = new Scanner(System.in);int c=0;for(;;){  int s=sc.nextInt();if(s==0)break;if(c!=0)System.out.println();String tn[] =new String[s];int tp[]=new int[s];  int tpc[]=new int[s];for(int i=0;i<s;i++){ tn[i]=sc.next();tp[i]=(sc.nextInt()*3+sc.nextInt()*0+sc.nextInt());tpc[i]=tp[i];}Arrays.sort(tpc);for(int i=tpc[s-1];i>-1;i--){ for(int j=0;j<s;j++) if(i==tp[j])System.out.println(tn[j]+","+tp[j]);}c++;}}}

Measured memory_bytes: 20560
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{ return firstElof.second < secondElof.second; }
//**Snippetリスト**//
//rep, vin, all//
//gcdlcm, isPrime, eratos, modinv, bitSearch, dfs, bfs, dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l, m, n; ll N, M, K, H, W, L; 
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 0;
vl flag, color; vll path; vl D;
//***********//
int main() {
	cin >> H >> W;
	vector<string> S(H);
	for (i = 0; i < H; i++) {
		cin >> S[i];
	}
	vll dp(H, vl(W, 0));
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	if (S[0][0] == '#')dp[0][0]++;
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (i != H-1) {
				dp[i+1][j] = min(dp[i+1][j], dp[i][j] + (S[i][j] == '.' && S[i+1][j] == '#'));
			}
			if (j != W-1) {
				dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (S[i][j] == '.' && S[i][j+1] == '#'));
			}
			//cout << "hoge";
		}
	}
	cout << dp[H-1][W-1];
}


Measured memory_bytes: 384
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val aa = readLine()!!.split(" ").map { it.toLong() }

    val fCnt = mutableMapOf<Long, Long>()
    var isPC = true

    outer@for (a in aa) {
        val factors = factors(a)
        for (k in factors.keys) {
            if (fCnt[k] != null) {
                isPC = false
                break@outer
            }
            fCnt[k] = 1L
        }
    }

    if (isPC) {
        println("pairwise coprime")
        return
    }

    val sc = aa.reduce { acc, i -> gcd(acc, i) }
    if (sc == 1L) {
        println("setwise coprime")
    } else {
        println("not coprime")
    }
}

fun gcd(a : Long, b : Long) : Long {
    return if (a % b == 0L) b else gcd(b, a % b)
}

fun factors(value: Long): Map<Long, Long> {
    val factors = mutableMapOf<Long, Long>()
    val max = Math.sqrt(value.toDouble()).toLong()
    var tmp = value

    for (i in 2..max) {
        while (tmp % i == 0L) {
            tmp /= i
            factors[i] = (factors[i] ?: 0) + 1
        }
    }

    if (tmp != 1L) {
        factors[tmp] = 1
    }

    return factors
}

Measured memory_bytes: 158828
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb emplace_back
#define x first
#define y second
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(auto i=(a); i<(b); i++)
#define dec(i,n,a) for(auto i=(n); i>=(a); i--)
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()
#define EPS 5e-9
#define fcin ios_base::sync_with_stdio(false)
#define db(x) cerr << #x << " == " << x << endl
#define _ << " " <<
#define MAXN 202020
#define LOGN 18
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;

int n, m;
ll x[MAXN], INF = 2e12, a, b;
vi adj[MAXN], cost[MAXN];

void dfs(int v){
	rep(i,0,sz(adj[v])){
		int u = adj[v][i], c = cost[v][i];
		if(x[u] == -INF){
			x[u] = x[v] + c;
			dfs(u);
		}
		if(x[u] != x[v] + c){
			puts("No");
			exit(0);
		}
	}
}

int main(){
	rep(i,0,MAXN) x[i] = -INF;
	scanf("%d%d", &n, &m);
	rep(i,0,m){
		int l, r, d;
		scanf("%d%d%d", &l, &r, &d);
		l--, r--;
		adj[l].pb(r);
		cost[l].pb(d);
		adj[r].pb(l);
		cost[r].pb(-d);
	}
	rep(i,0,n) if(x[i] == -INF){
		a = b = 0;
		x[i] = 0;
		dfs(i);
		if(b-a > 1000000000){
			puts("No");
			return 0;
		}
	}
	puts("Yes");
}


Measured memory_bytes: 25088
#include<bits/stdc++.h>
using namespace std;
int a[4],ans[4];
int main() {
	cin>>a[1]>>a[2]>>a[3];
	ans[1] = abs(a[1]-a[2]) + abs(a[1]-a[3]);
	ans[2] = abs(a[2]-a[1]) + abs(a[2]-a[3]);
	ans[3] = abs(a[3]-a[1]) + abs(a[3]-a[2]);
	cout<<min(ans[1],min(ans[2],ans[3]));
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200001];
int cnt[101];
int dp[101];
int n,k;
int dfs(int x,int up,int sum)
{
	if(x==-1)
		return sum;
	if(dp[x]&&up==0) return dp[x]+sum;
	int ans=0;
	if(up&&((k&(1ll<<x))==0))
		ans=dfs(x-1,1,sum+(1ll<<x)*cnt[x]);
	else if(up)
		ans=max(dfs(x-1,0,sum+(1ll<<x)*cnt[x]),
						 dfs(x-1,1,sum+(1ll<<x)*(n-cnt[x])));
	else
		ans=max(dfs(x-1,0,sum+(1ll<<x)*cnt[x]),
						 dfs(x-1,0,sum+(1ll<<x)*(n-cnt[x])));
	if(up==0) dp[x]=ans-sum;
	return ans;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	int ans,cur=0;
	for(int j=50;j>=0;j--)
	{
		int tot=0;
		for(int i=1;i<=n;i++)
			if(a[i]&(1ll<<j))
				cnt[j]++;
	}
	printf("%lld",dfs(50,1,0));
	return 0;
}
/*
3 1
1 6 3
*/

Measured memory_bytes: 1024
#include <stdio.h>

 int F[44];
 int fib(int);

 int main(){

   int n;

   scanf("%d",&n);

   printf("%d\n",fib(n));

   return 0;

 }

int fib(int n){

  if(n==0 || n==1)return F[n]=1;

  if(F[n]>1)return F[n];

  return F[n]=fib(n-2)+fib(n-1);

}

Measured memory_bytes: 2724
#!/usr/bin/env ruby
# require 'pry'

# dpテンプレ
# 最小化
# dp = Hash.new{ Float::INFINITY }
# dp[i] = [dp[i], dp[i-1] + hoge].min
# dp[0] = 0
# 最大化
# dp = Hash.new{ 0 }
# dp[i] = [dp[i], dp[i-1] + hoge].max
# dp[0] = 0

input = gets.chomp
# input = gets.split(' ').map(&:to_i)

puts input[0,3]


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

int main(){
    string str;
    int q;
    cin >> str >> q;

    for(int i = 0; i < q; i++ ){
        string command;
        int a, b;
        cin >> command >> a >> b;
        if(command == "print"){
            cout << str.substr(a, b-a+1) << endl;
        } 
        else if(command == "reverse"){
            string tmp = str.substr(a, b-a+1);
            int len = tmp.size();
            for(int j = 0; j < len; j++){
                str[j+a] = tmp[len-j-1];
            } 
        } 
        else{
            string p;
            cin >> p;
            str = str.replace(a, b-a+1, p);
        }
    }

    return 0;
}


Measured memory_bytes: 3220
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main(){
  vector<string> seg;
  int n, s;

    seg.push_back("0111111"); // 0
    seg.push_back("0000110"); // 1
    seg.push_back("1011011"); // 2
    seg.push_back("1001111"); // 3
    seg.push_back("1100110"); // 4 
    seg.push_back("1101101"); // 5 
    seg.push_back("1111101"); // 6 
    seg.push_back("0100111"); // 7
    seg.push_back("1111111"); // 8
    seg.push_back("1101111"); // 9


  while(cin >> n && n!=-1){
    //    if(n < 0 && n > 100) return 0;
    string start="0000000",ans="0000000";
    for(int i=0; i<n; i++){
      cin >> s;
      string result = seg[s];

      //cout << "start:  " << start << endl;
      //cout << "result: " << result << endl;

      for(int j=0; j<7; j++){
	if(start[j] == result[j]) ans[j] = '0';
	else ans[j] = '1';
      }

      cout << ans << endl;
      start = seg[s];
    }
  }
  return 0;
}

Measured memory_bytes: 0
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
INF = 10**10
def main(N, Ma, Mb, ABC):
    MX = 10 * N
    dp = [[[INF] * (MX + 1) for _ in range(MX + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        ni = i + 1
        ma, mb, mc = ABC[i]
        for na in range(MX + 1):
            a = na - ma
            for nb in range(MX + 1):
                b = nb - mb
                dp[ni][na][nb] = dp[i][na][nb]
                if a >= 0 and b >= 0:
                    dp[ni][na][nb] = min(dp[ni][na][nb], dp[i][a][b] + mc)

    ans = INF
    for a in range(MX + 1):
        for b in range(MX + 1):
            if a == 0 and b == 0: continue
            if a * Mb == b * Ma:
                ans = min(ans, dp[N][a][b])
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Ma, Mb = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, Ma, Mb, ABC)


Measured memory_bytes: 126608
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;

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

    string s;

    cin >> s;

    for (char i = 'a'; i <= 'z'; i++)
    {

        REP(j, s.size() - 1)
        {
            if (s[j] == i)
            {
                if (s[j + 1] == i || (j + 2 < s.size() && s[j + 2] == i))
                {
                    if (s.size() == 2)
                    {
                        cout << 1 << " " << 2 << endl;
                    }
                    else
                    {
                        if (j + 2 < s.size())
                            j++;

                        cout << j << " " << j + 2 << endl;
                    }
                    return 0;
                }
            }
        }
    }

    cout << "-1 -1" << endl;

    return 0;
}

Measured memory_bytes: 512