akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstring>
using namespace std;

int main(){
	int n,m,s;
	int dp[50][3001];
	while(1){
		cin >> n >> m >> s;
		if(n == 0 && m == 0 && s == 0) break;
		memset(dp,0,sizeof(dp));
		dp[0][0] = 1;
		for(int i=1;i<=m;i++){
			for(int j=n*n;j>0;j--){
				for(int l=i;l<=s;l++){
					dp[j][l] = (dp[j][l] + dp[j-1][l-i])%100000;
				}
			}
		}
		cout << dp[n*n][s] << endl;
	}
}

Measured memory_bytes: 1752
#include <iostream>
using namespace std;
 
int main() {
	double t, ans = -1;
	int a, b, c, d, e, f, water, sugar, aims;
	cin >> a >> b >> c >> d >> e >> f;
	t = 100.0/e;
	for(int i = 0; i < f/100; i++) {
		for(int j = 0; j < f/100-i; j++) {
			int w = 100 * (i*a + j*b);
			if(w == 0) continue;
			for(int s1 = 0; s1 <= f-w; s1++) {
				for(int s2 = 0; s2 <= f-w-s1; s2++) {
					int s = s1*c + s2*d;
					if(s*t <= w && s+w <= f) {
						if((100.0*s) / (w+s) > ans) {
							ans = (100.0*s)/(w+s);
							water = w;
							sugar = s;
						}
					}else break;
				}
			}
		}
	}
	cout << sugar+water << " " << sugar <<"\n";
	return 0; 
} 

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
	
#define WHATS(var)//cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}


	
int main() {
	ios::sync_with_stdio(false);
	int N;cin>>N;
	string answer;
	int now=0;
	stack<int>sta;
	for(int i=0;i<N;++i){
		int x;cin>>x;x--;
		while(x>=now){
			sta.emplace(now);
			now++;
			answer+="(";
		}
		if(sta.top()==x){
			sta.pop();
			answer+=")";
			
		}else{
			break;
		}
	}
	
	if(answer.size()!=2*N)answer=":(";
	cout<<answer<<endl;
	return 0;	
}


Measured memory_bytes: 3472
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
int main()
{
  int n,rem,ans,a,op;
  cin>>n;
  rem=n/1000;
  ans=rem*1000;
  a=n-ans;
  if(a>0)
     op=1000-a;
 else
    op=0;
  cout<<op<<endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

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

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;

constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main() {
    i64 N; cin>>N;
    i64 A,B;
    FOR(i,1,sqrt(N)+1) if (N%i==0) A=i,B=N/i;
    cout<<1+max(floor(log10(A)),floor(log10(B)))<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define vector2(a,b,c) vector<vector<int>> a(b/*縦！w*/,vector<int>(c/*横！w*/))
#define INF 1e10
#define MOD 1e9+7
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;
signed main(){
  int a,b,c,d,e;
  cin>>a>>b>>c>>d>>e;
  int f=min(d,e);
  int h=max(d,e);
  int g=0;
  if(a+b<=2*c)
    g+=(a+b)*f;
    else
      g+=c*2*f;
  int k;
  if(h==d)
    k=a;
  else
    k=b;
  if(k<c*2)
    g+=k*(h-f);
  else
    g+=c*2*(h-f);
  cout<<g<<endl;
}

Measured memory_bytes: 256
def main():
    D,G = map(int,input().split())
    score = []
    for i in range(D):
        p,c = map(int,input().split())
        score.append((p,c))
    ans = 2**60
    for mask in range(2**D):
        s = 0
        num = 0
        rest = -1
        for i in range(D):
            if (mask >> i&1):
                s += 100*(i+1)*score[i][0]+score[i][1]
                num += score[i][0]
            else:
                rest = i
        if s < G:
            s1 = 100*(rest+1)
            need = (G-s+s1-1)//s1
            if need >= score[rest][0]:
                continue
            num += need
        ans = min(ans,num)

    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <stdio.h>

#define N 100000
#define Q 50000

int binarySearch(int *A, int key, int length) {
	int mid;
	int left = 0;
	int right = length;

	while (left < right) {
		mid = (left + right) / 2;

		if (key == A[mid]) return 1;
		if (key > A[mid]) left = mid + 1;
		else if (key < A[mid]) right = mid;
	}

	return 0;
}

int main() {
	int n,q,i;
	int num = 0;
	int s[N], t[Q];

	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &s[i]);
	scanf("%d", &q);
	for (i = 0; i < q; i++) scanf("%d", &t[i]);

	for (i = 0; i < q; i++) num += binarySearch(s, t[i], n);

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

	return 0;
}

Measured memory_bytes: 1184
#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
using namespace std;

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
const int INF = (1 << 30);

//毎回変える定数
#define N_MAX 200


//変数
int N;
pair<int,int> l, r;
int ans = -1;

int ask(int num) {
	string res;
	cout << num << endl;
	cin >> res;
	switch (res[0]) {
	case 'M':
		return 0;
	case 'F':
		return 1;
	case 'V':
		ans = num;
		return 2;
	}
}

//サブ関数
//入力
void input()
{
	cin >> N;
	int res0 = ask(0);
	int resN = ask(N-1);

	l = make_pair(0, res0);
	r = make_pair(N - 1, resN);
}


//計算
void calc()
{
	int bef_num = -1;
	while (ans == -1) 
	{
		int mid = (l.first + r.first) / 2;
		if (bef_num == mid)mid++;
		else {
			bef_num = mid;
		}
		int res = ask(mid);
		if (res == 2)break;

		//DEBUGING("L:" << l.first << " " << l.second);
		//DEBUGING("R:" << r.first << " " << r.second);
		//DEBUGING("First:" << (res == l.second));
		//DEBUGING("Second:" << ((mid - l.first + 1) % 2 == 1));
		if ((res == l.second) == ((mid - l.first + 1) % 2 == 1)) {
			l = make_pair(mid, res);
		}
		else {
			r = make_pair(mid, res);
		}
	}
}


//出力
void output()
{
}

//デバッグ
void debug(){
	int N;
	cin>>N;
}


//メイン関数
int main(){
	
	input();
	calc();
	output();
	//debug();
	
	return 0;
}


Measured memory_bytes: 852
fun main(args: Array<String>) {
    val n = readInt()
    val a = readIntList()
    if (a.distinct().size == a.size) println("YES")
    else println("NO")
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int cal(vector<int> v)
{
  return (v[2] - v[0]) / 2 + (v[2] - v[1]) / 2;
}

int main()
{
  vector<int> v(3);
  scanf("%d %d %d", &v[0], &v[1], &v[2]);
  sort(v.begin(), v.end());
  int bsum = (v[0] & 1) + (v[1] & 1) + (v[2] & 1);
  int ans = 0;
  switch (bsum) {
    case 0:
      // all even
      ans = cal(v);
      break;
    case 1:
      // one odd, two even
      for (int i = 0; i < (int)v.size(); ++i) {
        if ((v[i] & 1) == 0) { ++v[i]; }
      }
      ans = 1 + cal(v);
      break;
    case 2:
      // two odd, one even
      for (int i = 0; i < (int)v.size(); ++i) {
        if (v[i] & 1) { ++v[i]; }
      }
      ans = 1 + cal(v);
      break;
    case 3:
      // all odd
      ans = cal(v);
      break;
    default:
      printf("This canot be!\n");
      return -1;
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 256
# import sys; sys.stdin = open('input.txt')

s = raw_input()

a = []
for c in s:
	if c == 'S':
		a.append(c)
	else:
		if len(a) > 0 and a[-1] == 'S':
			a.pop()
		else:
			a.append(c)

print len(a)	


Measured memory_bytes: 4456
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

long gcd(long a, long b)
{

    long r, tmp;
    /* 自然数 a > b を確認・入替 */
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
 
    /* ユークリッドの互除法 */
    r = a % b;
    while(r!=0){
        a = b;
        b = r;
       r = a % b;
    }
	return b;
}

vector<long> decompositPrime(long n){
    vector<long> primes;
    long div = 2;
    while( n >= div * div){
        if(n%div ==0){
            primes.push_back(div);  
            n /= div;
        } else {
            div++;
        }
    }
    //最後に残ったのは素因数
    primes.push_back(n);

    return primes;
}


int main() {
    long A;
    long B;
    cin >> A >> B ;

    long gcdVal = gcd(B,A);

    vector<long> primes = decompositPrime(gcdVal);

    long count = 1; // 1は必ず含まれる
    long bef = 1; 
    for(auto prime: primes){
        if(bef != prime){
            count++;
        }
        bef = prime;
    } 

    cout << count << endl;

    return 0;
}



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

  int H, W;
  vector<string> row;
  vector<string> row2;

int count_current_row(vector<string> row, int i, int j){
  int ans = 0;
    if (j==0 && W ==1){
  }else if(j == 0){
    if(row.at(i).at(j+1) == '#') ans++;
  }else if (j == W-1){
    if(row.at(i).at(j-1) == '#') ans++;
  }else{
    ans += (row.at(i).at(j-1) =='#') + (row.at(i).at(j+1) == '#');
  }
  return ans;
}

int count_upper_row(vector<string> row, int i, int j){
  int ans = 0;
  if (j==0 && W ==1){
    ans +=  (row.at(i-1).at(j) == '#');
  }else if(j == 0){
    ans += (row.at(i-1).at(j) =='#') + (row.at(i-1).at(j+1) == '#');
  }else if (j == W-1){
    ans += (row.at(i-1).at(j-1) =='#') + (row.at(i-1).at(j) == '#');
  }else{
    ans += (row.at(i-1).at(j-1) =='#') + (row.at(i-1).at(j) == '#') + (row.at(i-1).at(j+1) == '#');
  }
  return ans;
}

int count_lower_row(vector<string> row, int i, int j){
  int ans = 0;
  if (j==0 && W ==1){
    ans +=  (row.at(i+1).at(j) == '#');
  }else if(j == 0){
    ans += (row.at(i+1).at(j) =='#') + (row.at(i+1).at(j+1) == '#');
  }else if (j == W-1){
    ans += (row.at(i+1).at(j-1) =='#') + (row.at(i+1).at(j) == '#');
  }else{
    ans += (row.at(i+1).at(j-1) =='#') + (row.at(i+1).at(j) == '#') + (row.at(i+1).at(j+1) == '#');
  }
  return ans;
}


int count(vector<string> row, int i, int j){
  int ans = 0;
  if (i == 0 && H == 1){
    ans += count_current_row(row,i,j);
  }
  else if(i == 0){
    ans += count_current_row(row, i,j);
    ans += count_lower_row(row, i,j);
  }else if(i == H-1){
    ans += count_upper_row(row, i,j);
    ans += count_current_row(row, i,j);
  }else{
    ans += count_upper_row(row, i,j);
    ans += count_current_row(row,i,j);
    ans += count_lower_row(row,i,j);
  }
  return ans;
}

char convert(int a){
 if(a == 0) return '0'; 
 else if(a == 1) return '1'; 
 else if(a == 2) return '2';
 else if(a == 3) return '3';
 else if(a == 4) return '4';
 else if(a == 5) return '5';
 else if(a == 6) return '6';
 else if(a == 7) return '7';
 else if(a == 8) return '8';
//  else cout << "conversion error" << endl;
}

int main() {

  cin >> H >> W;
  vector<string> row(H);
  for(int i = 0; i < H; i++){
    cin >> row.at(i);
  }
  
  vector<string> row2(H);

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      row2.at(i).push_back('#'); //initialization
    }
  }

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

    for(int j = 0; j < W; j++){
      if(row.at(i).at(j) != '#'){
        row2.at(i).at(j) = convert(count(row,i,j));
      }
    }
  }
  for(int i = 0; i < H; i++){
    cout << row2.at(i) << endl;
  } 
  
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val cList = mutableListOf(0)
    val sList = mutableListOf(0)
    val fList = mutableListOf(0)
    for (i in 1..(n - 1)) {
        val (c, s, f) = readLine()!!.split(" ").map(String::toInt)
        cList.add(c)
        sList.add(s)
        fList.add(f)
    }

    for (i in 1..(n - 1)) {
        var t = 0L
        for (j in i..(n - 1)) {
            if (t <= sList[j]) {
                t = (sList[j] + cList[j]).toLong()
            } else if (t % fList[j] == 0L) {
                t += cList[j]
            } else {
                t += cList[j] + (fList[j] - t % fList[j])
            }
        }
        println(t)
    }
    println(0)
}


Measured memory_bytes: 37564
#include <bits/stdc++.h>
#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 INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

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

int main()
{
	string s;
	cin >> s;
	int kind[26] {0};

	int len = (int)s.size();
	REP(i, len){
		kind[s[i] - 'a']++;
		if (kind[s[i] - 'a'] > 1){
			cout << "no" << endl;
			return 0;
		}
	}

	cout << "yes" << endl;
}


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

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

    string s = S.substr(0,4)+S.substr(5,2)+S.substr(8,2);
    
    if(s <= "20190430"){
        cout << "Heisei" << endl;
    }else{
        cout << "TBD" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define RAP(i, n) for(ll i=0;i<(n);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)

int main(){
  ll s, w;
  cin >> s >> w;
  if(w >= s){
    cout << "unsafe" << endl;
  }else{
    cout << "safe" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int a,b;
    cin >> a >> b;
    cout << a*b << endl;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
const 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 main()
{
  int k;
  cin>>k;
  cout<<a[k-1];
  return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <climits> 
#include <assert.h>
#include <random>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int d;
    cin >> d;
    vector<int> c(26);
    for(int i=0; i<26; i++) cin >> c[i];
    vector<vector<int>> G(d,vector<int> (26));
    for(int i=0; i<d; i++){
        for(int j=0; j<26; j++){
            cin >> G[i][j];
        }
    }
    vector<int> t(d);
    for(int i=0; i<d; i++){
        t[i] = rand() % 26;
    }
    int sum = 0;
    for(int k=0; k<100000; k++){
        int a = rand() % d;
        int b = rand() % 26;
        int pre = t[a];
        t[a] = b;
        vector<int> now(26,0);
        vector<int> last(26,0);
        for(int i=0; i<d; i++){
            last[t[i]] = i+1;
            now[t[i]] += G[i][t[i]];
            for(int j=0; j<26; j++){
                now[t[i]] -= c[j] * (i+1 - last[j]);
            }
        }
        int s = 0;
        for(int j=0; j<26; j++){
            s += now[j];
        }
        if(s > sum){
            sum = s;
        }else{
            t[a] = pre;
        }
    }
    for(int i=0; i<d; i++){
        cout << t[i]+1 << "\n";
    }
    return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

struct point{
    int x, y;
};

double distancee(point a, point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}


int main(){
    int n;

    cin >> n;

    vector <point> p(n);
    double answ = 0, facN = 1;

    for (int i = 0; i < n; i++)
        cin >> p[i].x >> p[i].y;

    for (int i = 1; i <= n - 1; i++)
            facN *= i;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++){
            if (i != j)
                answ += distancee(p[i], p[j]) * facN;
        }
    cout << fixed << setprecision(6) << answ / (facN * n);


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    int ng = 0, ok = INF<int>;
    while(ok-ng > 1){
        int mid = (ok+ng)/2;
        ll val = 0;
        for (int i = 0; i < n; ++i) {
            if(v[i] >= mid+1){
                val += (v[i]-1)/mid;
            }
        }
        if(val <= k) ok = mid;
        else ng = mid;
    }
    cout << ok << "\n";
    return 0;
}

Measured memory_bytes: 3960
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int int32_t
#define all(c) c.begin(), c.end()
#define FAST ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define bitcnt(n) __builtin_popcountll(n)
#define setpre(n) cout << fixed << setprecision(n)
#define tr(c) for(const auto& x : c )cout << x << " "; cout << "\n";
#define ol(c, s, e) for(int pos=s; pos<e; pos++)cout << c[pos] << " ";cout <<"\n";
#define PI acos(-1LL)

const int M = 1000000007;
const int N = 2e5 + 5;
const long long INF = 1e9 + 12;

vector<vector<int>> v;
int n, weight;
int dp[105][N];
int fun(int i = n-1, int w = weight){
    if(w < 0)
        return -INF;
    if(i < 0)
        return 0;
    if(dp[i][w]!=-1)
        return dp[i][w];
    int ans = max(fun(i-1,w - v[i][0]) + v[i][1], fun(i-1,w));
    return dp[i][w] = ans;
}
void solve() {
    cin >> n >> weight;
    v.resize(n, vector<int>(2));
    memset(dp, -1, sizeof dp);
    for(int i=0; i<n; i++){
        cin >> v[i][0] >> v[i][1];
    }
    cout << fun();
}

signed main(){
    FAST
    int tc = 1;
//    TODO: check for tc
//    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}


Measured memory_bytes: 167724
N,K = map(int,input().split())
d = {}
for i in range(N):
    a,b = map(int,input().split())
    if a in d:
        d[a]=d[a]+b
    else:
        d.setdefault(a,b)

d = sorted(list(d.items()))

for i in range(len(d)):
    K = K - d[i][1]
    if K <= 0:
        print(d[i][0])
        break

Measured memory_bytes: 15072
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	sc := NewScanner()

	s := sc.ReadString()
	t := sc.ReadString()

	maxCommonLen := 0
	for startPos := 0; startPos+len(t) <= len(s); startPos++ {
		commonLen := 0
		for i := 0; i < len(t); i++ {
			if t[i] == s[startPos+i] {
				commonLen++
			}
		}
		if commonLen > maxCommonLen {
			maxCommonLen = commonLen
		}
	}

	fmt.Println(len(t) - maxCommonLen)
}

// from [my library](https://github.com/ikngtty/go-contestlib)
// -   math/simple

func Abs(x int) int {
	if x >= 0 {
		return x
	}
	return -x
}

func Min(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}

	min := values[0]
	for _, v := range values {
		if v < min {
			min = v
		}
	}
	return min
}

func Max(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}

	max := values[0]
	for _, v := range values {
		if v > max {
			max = v
		}
	}
	return max
}

func Pow(base, exponent int) int {
	if exponent < 0 {
		panic(fmt.Sprintf("exponent (%d) should not be a minus", exponent))
	}

	answer := 1
	for i := 0; i < exponent; i++ {
		answer *= base
	}
	return answer
}

func Ceil(divident, dividor int) int {
	if dividor == 0 {
		panic("dividor should not be 0")
	}

	quo := divident / dividor
	rem := divident % dividor

	if rem != 0 {
		if (divident > 0 && dividor > 0) ||
			(divident < 0 && dividor < 0) {
			return quo + 1
		}
	}
	return quo
}

// -   sortutil

func ReverseInts(a []int) {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
}

func ReverseStrings(a []string) {
	sort.Sort(sort.Reverse(sort.StringSlice(a)))
}

// -   io

type Scanner struct {
	bufScanner *bufio.Scanner
}

func NewScanner() *Scanner {
	bufSc := bufio.NewScanner(os.Stdin)
	bufSc.Split(bufio.ScanWords)
	bufSc.Buffer(nil, 100000000)
	return &Scanner{bufSc}
}

func (sc *Scanner) ReadString() string {
	bufSc := sc.bufScanner
	bufSc.Scan()
	return bufSc.Text()
}

func (sc *Scanner) ReadInt() int {
	bufSc := sc.bufScanner
	bufSc.Scan()
	text := bufSc.Text()

	num, err := strconv.Atoi(text)
	if err != nil {
		panic(err)
	}
	return num
}

func (sc *Scanner) ReadFloat() float64 {
	bufSc := sc.bufScanner
	bufSc.Scan()
	text := bufSc.Text()

	num, err := strconv.ParseFloat(text, 64)
	if err != nil {
		panic(err)
	}
	return num
}


Measured memory_bytes: 1776
n=int(input())
l=[[] for x in range(4)]
list_=["S","H","C","D"]
set_=set([x for x in range(1,14)])
for i in range(n):
    a,b=input().split()
    l[list_.index(a)].append(int(b))
#print(l)
#for m in len(l):
for m in range(len(l)):
    l_=sorted(list(set_-set(l[m])))
    for n in l_:
        print(list_[m],n)


Measured memory_bytes: 5604
#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a(3);
    for(int i=0;i<3;i++){
        cin >> a.at(i);
    }
    sort(a.begin(),a.end());
    for(int i=0;i<2;i++){
        cout << a.at(i) << ' ';
    }
    cout << a.at(2) << endl;
}


Measured memory_bytes: 3156
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(M)]

for i in range(N):
    a, b = AB[i]
    x = abs(CD[0][0]-a)+abs(CD[0][1]-b)
    y = 0
    for j in range(1, M):
        c, d = CD[j]
        ky = abs(c-a)+abs(d-b)
        if ky < x:
            x = ky
            y = j
    print(y+1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int x; cin >> x;
    if (x < 1200) cout << "ABC" << endl;
    else cout << "ARC" << endl;
}

Measured memory_bytes: 256
//ssenseeeeeeeeeeeeeeeeeeeeeeeeeeeee
#include<bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef unsigned long long ull;
typedef long long  ll;
#define MOD 1000000007
#define MX 1000000000
#define NMAX 100005
#define MXL 1000000000000000000
#define PI 3.14159265
#define pb push_back
using namespace std;
#define sc second
#define endl '\n'
#define fr first
//read contraints to make sure its not brute force

int main()
{
    int n;
    cin >> n;
    pair<int, int> a[n+1];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i].fr >> a[i].sc;
    }
    for(int i = 0; i < n-2; i++)
    {
        if(a[i].fr == a[i].sc && a[i+1].fr == a[i+1].sc && a[i+2].fr == a[i+2].sc)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}



Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;
const int mod = 998244353;
struct mint {
    ll x;
    mint(ll x=0):x(x%mod){}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};
int main() {
    int n; cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    rep(i, n) {
        cin >> a[i];
        sum += a[i];
    }
    //rの合計がv
    vector< vector<mint> > dp(n+1,vector<mint>(sum+1,0));
    dp[0][0] = 1;
    //合計がv
    auto dp2 = dp;
    rep(i, n) {
        for(int v=0; v+a[i]<=sum; v++) {
            //i番目をrの要素
            dp[i+1][v+a[i]] += dp[i][v];
            //g,bの要素
            dp[i+1][v] += dp[i][v]*2;
            
            dp2[i+1][v+a[i]] += dp2[i][v];
            dp2[i+1][v] += dp2[i][v];
        }
    }
    mint three(3);
    mint all = three.pow(n);
    mint hosyugo = 0;
    for(int i=sum/2+1;i<=sum;i++) hosyugo += dp[n][i] * 3;
    if(sum%2 == 0) {
        hosyugo += (dp[n][sum/2] - dp2[n][sum/2] * 2) * 3;
        hosyugo += dp2[n][sum/2] * 3;
    }
    cout << (all - hosyugo).x;
}


Measured memory_bytes: 423104
import java.util.Scanner;

public class Main {

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

        int A = sc.nextInt();
        int B = sc.nextInt();
		int C = sc.nextInt();
		int K = sc.nextInt();


        System.out.println(calc(A, B, C, K));
    }

    public static int calc(int A, int B, int C, int K) {

		int mid = Integer.max(A, B);
//		System.out.println("mid:" + mid);
		int low = Integer.min(A, B);
//		System.out.println("low:" + low);
		int max = Integer.max(mid, C);
		mid = Integer.min(mid, C);
//		System.out.println("max:" + max);

		int total = max;

		for (int i = 1; i <= K; i++) {
			total = total * 2;
//			System.out.println("total:" + total);
		}

		total = total + mid + low;
//		System.out.println("total:" + total);
		return total;
	}
}

Measured memory_bytes: 23124
N,K=map(int,input().split())

M=N+1

A=-M*(M+1)*(2*M+1)//6+(N+1)*M*(M+1)//2+M

M=K-1

B=-M*(M+1)*(2*M+1)//6+(N+1)*M*(M+1)//2+M


print((A-B)%(10**9+7))

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


int main(){
	int n;
	cin >>n;
	int A[n],B[n],C[n];
	for(int i=0;i<n;i++){
		cin >>A[i];
	}
	for(int i=0;i<n;i++){
		cin >>B[i];
	}
	for(int i=0;i<n-1;i++){
		cin >>C[i];
	}
	long total=B[A[0]-1];
	for(int i=1;i<n;i++){
		total+=B[A[i]-1];
		if((A[i-1]+1)==A[i]){
			total+=C[A[i-1]-1];
		}
	}
	cout <<total<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
    #define endl "\n"
    #define pb push_back
    typedef long long ll;
    queue<int>q;
    int nums[200001];
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        ll ans=0;
        int n,hi=0,idx=0;
        cin>>n;
        for(int i=0;i<n;++i){
            cin>>nums[i];
            if(nums[i]>hi){
                hi=nums[i];
                idx=i;
            }
        }
        for(int i=idx+1;i<n;++i){
            ans+=abs(nums[i]-nums[i-1]);
            nums[i]=nums[i-1];
        }
        for(int i=1;i<=idx;++i){
            if(nums[i]<nums[i-1]){
                ans=ans+nums[i-1]-nums[i];
                nums[i]=nums[i-1];
            } 
        }
        cout<<ans<<endl;
    
    }

Measured memory_bytes: 4436
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

lli A[200000] = {};
lli B[200000] = {};

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

	FOR(N)
		cin >> A[i],B[i] = A[i];

	sort(A, A + N);

	FOR(N) {
		if (B[i] == A[N - 1]) {
			COUT(A[N - 2]);
		}
		else {
			COUT(A[N - 1]);
		}
	}

	return 0;
}

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

using namespace std;

int main(){
 int r0,w0,c,r,i;
 while(cin >> r0 >> w0 >> c >> r && r0){
  i=0;
  while((r0+i*r)/w0 < c)i++;
  cout << i << endl;
 }
 return 0;
}


Measured memory_bytes: 3064
function Main(input){
	inputs = input.split('\n');
    H = Number(inputs[0].split(' ')[0]);
    W = Number(inputs[0].split(' ')[1]);
    h = Number(inputs[1].split(' ')[0]);
    w = Number(inputs[1].split(' ')[1]);
    ans = (H-h)*(W-w);
    console.log(ans);
} 
 
Main(require("fs").readFileSync("/dev/stdin","utf8"));

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  string s; cin>>s;
  ll n=s.size();
  string a="dream", b="dreamer", c="erase", d="eraser";
  reverse(all(a));
  reverse(all(b));
  reverse(all(c));
  reverse(all(d));
  reverse(all(s));
  ll pos=0;
  
  while(pos<n){
    if(n-pos>=5){
      if(s.substr(pos,5)==a || s.substr(pos,5)==c){
        pos+=5;
        continue;
      }
    }
    if(n-pos>=6){
      if(s.substr(pos,6)==d){
        pos+=6;
        continue;
      }
    }
    if(n-pos>=7){
      if(s.substr(pos,7)==b){
        pos+=7;
        continue;
      }
    }
    cout<<"NO"<<endl;
    return 0;
  }
  cout<<"YES"<<endl;
}

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

int main(){
    long long n,ans=0;
    cin>>n;
    for(long long i=1;i<=n;i++){
        if(i*i<=n) ans=i*i;
        else break;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int ans = 1;

void grid_bfs(vector< string > &s, char start, const string &wall = "#") {
	const int vx[] = { 0, 1, 0, -1 }, vy[] = { 1, 0, -1, 0 };
	vector< vector< int > > min_cost(s.size(), vector< int >(s[0].size(), -1));
	queue< pair< int, int > > que;
	for (int i = 0; i < s.size(); i++) {
		for (int j = 0; j < s[i].size(); j++) {
			if (s[i][j] == start) {
				que.emplace(i, j);
				min_cost[i][j] = 0;
			}
		}
	}

	while (!que.empty()) {
		auto p = que.front();
		que.pop();
		for (int i = 0; i < 4; i++) {
			int ny = p.first + vy[i], nx = p.second + vx[i];
			if (nx < 0 || ny < 0 || nx >= s[0].size() || ny >= s.size()) continue;
			if (min_cost[ny][nx] != -1) continue;
			if (wall.find(s[ny][nx]) != string::npos) continue;
			min_cost[ny][nx] = min_cost[p.first][p.second] + 1;
			ans = max(ans, min_cost[ny][nx]);
			que.emplace(ny, nx);
		}
	}
}

int main() {
	int h, w; cin >> h >> w;
	vector<string> tb(h);
	for (int i = 0; i < h; i++) {
		cin >> tb[i];
	}

	
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char tmp = tb[i][j];
			if (tmp == '#')continue;
			tb[i][j] = 's';
			grid_bfs(tb,'s',"#");
			tb[i][j] = tmp;
		}
	}

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <functional>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <cstdio>


using namespace std;

typedef long long ll;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main(int argc, char **argv)
{
    ll N;
    ll K;
    cin >> N >> K;
    ll A[N], F[N];
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> F[i];

    sort(A, A + N);
    sort(F, F + N, greater<int>());
    ll start, end;
    start = 0;
    end = 1e+14;
    ll target = (end + start) / 2;
    while (start != target) {
        ll resK = K;
        bool f = true;
        REP(i, N) {
            if (A[i] * F[i] > target) {
                ll x = A[i] - target / F[i];
                if (resK < x) {
                    f = false;
                    break;
                }
                else {
                    resK -= x;
                }
            }
        }
        if (f) end = target;
        else start = target;
        target = (end + start) / 2;
    }
    ll resK = K;
    bool f = true;
    REP(i, N) {
        if (A[i] * F[i] > target) {
            ll x = A[i] - target / F[i];
            if (resK < x) {
                f = false;
                break;
            }
            else {
                resK -= x;
            }
        }
    }
    if (f) cout << target << endl;
    else cout << target + 1 << endl;

    return 0;
}


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

using namespace std;

#define MAX 300001
typedef unsigned long long ull;
const ull B = 1000000007ULL;

int main(){
    int N,M;
    char s[MAX];
    scanf("%d%d%s",&N,&M,s);
    vector<ull> p(N+1),hash(N+1);
    p[0] = 1; hash[0] = 0;
    for(int i = 0 ; i < N ; i++){
        hash[i+1] = hash[i]*B + s[i];
        p[i+1] = p[i]*B;
    }
    int L = 0, R = 0;
    set<ull> st;
    while(M--){
        scanf("%s",s);
        if(s[0] == 'L' && s[1] == '+'){
            L++;
        }else if(s[0] == 'L' && s[1] == '-'){
            L--;
        }else if(s[0] == 'R' && s[1] == '+'){
            R++;
        }else{
            R--;
        }
        st.insert(hash[R+1]-hash[L]*p[R-L+1]);
    }
    printf("%d\n",(int)st.size());
    return 0;
}

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

public class Main {
	
	public static void main(String[] args) {
		FastReader scan = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		Task solver = new Task();
		solver.solve(1, scan, out);
		out.close();
	}
	
	static class Task {
		public void solve(int testNumber, FastReader scan, PrintWriter out) {
			int n = scan.nextInt();
			String[] a = new String[n];
			for(int i = 0; i < n; i++) a[i] = convert(scan.next());
			Arrays.sort(a);
			long at = 0, total = 0;
			String curr = "";
			for(int i = 0; i < n; i++) {
				if(a[i].equals(curr)) at++;
				else {
					total += at*(at-1)/2;
					at = 1;
					curr = a[i];
				}
			}
			total += at*(at-1)/2;
			out.println(total);
		}
		
		static String convert(String s) {
			ArrayList<Character> x = new ArrayList<>();
			for(char c : s.toCharArray()) x.add(c);
			Collections.sort(x);
			char[] res = new char[s.length()];
			for(int i = 0; i < res.length; i++) res[i] = x.get(i);
			return new String(res);
		}
	}
	
	

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int h, w;
string s[52];

int main() {
	cin >> h >> w;
	inc(i, w + 2) { s[0] += "."; }
	inc1(i, h) { cin >> s[i]; s[i] = "." + s[i] + "."; }
	inc(i, w + 2) { s[h + 1] += "."; }
	
	inc1(i, h) {
	inc1(j, w) {
		if(s[i][j] != '.') { continue; }
		s[i][j] = '0';
		incII(ii, -1, 1) {
		incII(jj, -1, 1) {
			if(s[i + ii][j + jj] == '#') { s[i][j]++; }
		}
		}
	}
	}
	
	inc1(i, h) {
	inc1(j, w) {
		cout << s[i][j];
	} cout << "\n";
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>

using namespace std;

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

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repi(i, j, n) for(int i = j;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define F first
#define S second

// #define COMMENT

/*

const int NN = 200090;
ll fact[NN];
ll finv[NN];
ll inv[NN];

void inverse_modulao() {
  fact[0] = fact[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;

  for(int i = 2;i < NN;i++) {
    fact[i] = fact[i-1]*i%mod;
    inv[i] = mod-mod/i*inv[mod%i]%mod;
    finv[i] = finv[i-1]*inv[i]%mod;
  }
}

ll nCr(int n, int r) {
  return fact[n]*finv[r]%mod*finv[n-r]%mod;
}

*/

int n, m, k, xi, yi, xj, yj;
string s[1<<20];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

#define dist_state pair<int,pair<pii, int>>

int dijkstra() {

  const int INF = 1e8;
  vector<vector<vector<int>>> dist =
  vector<vector<vector<int>>>(n+3,
    vector<vector<int>>(m+3,
      vector<int>(6, INF)));

  set<pair<int,pair<pii, int>>> pq;
  rep(i, 4) {
    pq.insert({0, {{xi, yi}, i}});
    dist[xi][yi][i] = 0;
  }

  while(!pq.empty()) {
    dist_state ds = *pq.begin();
    pq.erase(pq.begin());

    int dxs = 4;
    for(int i = 0;i < dxs;i++) {
      if(!(dx[i] + dx[ds.S.S] == 0 && dy[i] + dy[ds.S.S] == 0)) {
        int x = ds.S.F.F + dx[i], y = ds.S.F.S + dy[i], cnt = 1;
        while(x >= 0 && y >= 0 && x < n && y < m && cnt <= k && s[x][y] == '.') {
          if((ds.F + 1) < dist[x][y][i]) {
            pq.erase({dist[x][y][i], {{x, y}, i}});
            pq.insert({1+ds.F, {{x, y}, i}});
            dist[x][y][i] = 1+ds.F;
          } else if((ds.F + 1) > dist[x][y][i]) break;
          cnt++;
          x += dx[i];
          y += dy[i];
        }
      }
    }
  }

  int ans = INF;
  rep(i, 4) ans = min(ans, dist[xj][yj][i]);
  return (ans == INF ? -1 : ans);
}

int main() {

// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
  cin>>n>>m>>k;
  cin>>xi>>yi>>xj>>yj;
  xi--;yi--;xj--;yj--;
  rep(i,n) cin>>s[i];

  cout << dijkstra() << endl;

  return 0;
}


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

int main(){
    ll n; cin >> n;
    vector<ll> x(n), y(n); rep(i,n) cin >> x[i];

    y = x;

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

    for(long long i = 0; i < n; i++){
        if(y[i] < x[n/2]){
            put(x[n/2]);
        }else{
            put(x[n/2-1]);
        }
    }
}

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

const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main() {
    int N, K;
    cin >> N >> K;
 
    vector<ll> kind[N];
    for (int i = 0; i < N; ++i) {
        int t;
        ll d;
        cin >> t >> d;
        --t;
        kind[t].push_back(d);
    }
 
    vector<ll> best, res;
    for (int i = 0; i < N; ++i) {
        if (!kind[i].empty()) {
            sort(kind[i].begin(), kind[i].end());
            best.push_back(kind[i].back());
            kind[i].pop_back();
 
            while (!kind[i].empty()) {
                res.push_back(kind[i].back());
                kind[i].pop_back();
            }
        }
    }
 
    sort(best.rbegin(), best.rend());
    sort(res.rbegin(), res.rend());
 
    vector<ll> bsum = {0};
    for (int i = 0; i < best.size(); ++i) {
        bsum.push_back(bsum.back() + best[i]);
    }
 
    vector<ll> rsum = {0};
    for (int i = 0; i < res.size(); ++i) {
        rsum.push_back(rsum.back() + res[i]);
    }
    while (rsum.size() < K) rsum.push_back(0);
 
    ll ans = 0;
    for (ll x = 1; x <= min(K, (int)best.size()); ++x) {
        ans = max(ans, bsum[x] + rsum[K - x] + x * x);
    }
 
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8180