akhauriyash/Code-Regression huggingface dataset:
fn main() {
    proconio::input! {
        s: proconio::marker::Chars,
    }
    let mut remove_pair_count = 0usize;
    let mut s_count = 0usize;
    for &c in &s {
        match c {
            'S' => {
                s_count += 1;
            }
            'T' => {
                if s_count > 0 {
                    remove_pair_count += 1;
                    s_count -= 1;
                }
            }
            _ => unreachable!(),
        }
    }
    let ans = s.len() - remove_pair_count * 2;
    println!("{}", ans);
}


Measured memory_bytes: 3028
S = list(input())
S = list(set(S))
count = 0

Alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

for a in Alpha:
    for s in S:
        if s != a:
            count += 1
        else:
            break
        
    if  count == len(S):
        print(a)
        exit()
    else:
        count = 0

print('None')

Measured memory_bytes: 3956
N,W=map(int,input().split())

dp=[[0,0] for i in range(100001)]

dp[0][0]=1

w=[]
v=[]

for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

for i in range(N):
    for j in range(100001):
        if dp[100001-1-j][0]==1:
            dp[100001-1-j+v[i]][0]=1
            if dp[100001-1-j+v[i]][1]>0:
                dp[100001-1-j+v[i]][1]=min(dp[100001-1-j][1]+w[i],dp[100001-1-j+v[i]][1])
            else:
                dp[100001-1-j+v[i]][1]=dp[100001-1-j][1]+w[i]
ans=0
for i in range(100001):
    if dp[i][0]==1 and dp[i][1]<=W and i>ans:
        ans=i
print(ans)

Measured memory_bytes: 53360
import java.util.*;

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

        if (A > 8 || B > 8) {
            System.out.println(":(");
        } else {
            System.out.println("Yay!");
        }
    }
}


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

long long fac(long long n) {
    long long res = 1;
    for (long long i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

void nextPermutation(vector<int>& a){ // n — длина перестановки
    int n = a.size();
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] < a[i + 1]) {
            int mn = i + 1;
            for (int j = i + 1; j <= n - 1; j++)
                if (a[j] < a[mn] && a[j] > a[i])
                    mn = j;
            swap(a[i], a[mn]);
//            cout << i << " " << mn << endl;
            reverse(a.begin() + i + 1, a.end());
            return;
        }
    }
}

double sqr(double v) {
    return v * v;
}

int main() {
    int n;
    cin >> n;
    vector<double> x(n), y(n);
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        v[i] = i;
    }
    double nn = fac(n);
    double ans = 0;
    for (int i = 0; i < nn; i++) {
        for (int j = 0; j < n - 1; j++) {
            ans+= sqrt(sqr(x[v[j]] - x[v[j + 1]]) + sqr(y[v[j]] - y[v[j + 1]]));
//            cout << v[j] << " ";
        }
//        cout << v[n - 1] << endl;
        nextPermutation(v);
    }
//    cout << ans << endl;
    cout << fixed << setprecision(10) << ans / nn;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
struct hiro {
	int high, low;
};
int main(void) {
	struct hiro data[7];
	for (int i = 0; i < 7; i++) {
		scanf("%d%d", &data[i].high, &data[i].low);
	}
	for (int i = 0; i < 7; i++) {
		printf("%d\n", data[i].high-data[i].low);
	}
	return 0;
}


Measured memory_bytes: 2104
#include<iostream>
#include<vector>
using namespace std;
#define int long long
#define V vector
#define vel V<int>
#define rep(i,n) for(int i=0;i<n;i++)
#define mkp make_pair
#define pin pair<int,int>
pin solve(V<pin>& ab, int ex) {
	if (!ex) { return mkp(1,0); }
	V<V<pin>> qab(2);
	for (pin x : ab) {
		qab[x.second & 1].push_back(mkp(x.first / 2,x.second / 2));
		if (x.first & 1) { qab[(x.second + 1) & 1].push_back(mkp(x.first / 2,(x.second + 1) / 2)); }
	}
	V<vel> c(2, vel(2));
	rep(i, 2) {
		for (pin x : qab[i]) {
			int qc = (2 * x.first + x.second) % 3;
			if ((qc+1)%2) { c[i][0] ^= 1; }
			if (qc) { c[i][1] ^= 1; }
		}
	}
	rep(i, 2) {
		if (!c[1 - i][0]&&!c[1-i][1]) {
			pin ans = solve(qab[i], ex - 1);
			ans.first *= 2; ans.second *= 2; ans.second += i;
			return ans;
		}
	}
	for(pin &v:ab) { v.first++; }
	pin ans = solve(ab, ex); ans.first--;
	return ans;
}
signed main() {
	long long inf = 2e17;
	int n; scanf("%lld", &n);
	V<pin> ab(n);
	rep(i, n) {
		long long a, b; scanf("%lld", &a); scanf("%lld", &b);
		ab[i] = { a + inf,b + inf };
	}
	pin ret = solve(ab, 70);
	cout << ret.first - inf << " " << ret.second - inf << "\n";
}

Measured memory_bytes: 11632
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int n,K,m;
ll f[305][305],c[605][605],s[305][305];
int main(){
	scanf("%d%d%d",&n,&K,&m);
	const int mod=m;
	for(int i=0;i<=602;i++){
		c[i][0]=1;
		for(int p=1;p<=i;p++) c[i][p]=(c[i-1][p]+c[i-1][p-1])%mod;
	}
	for(int i=1;i<=K;i++) s[1][i]=K-i+1,f[1][i]=K-i+1;
	for(int i=2;i<=n;i++){
		for(int p=K;p;p--) s[i][p]=(s[i][p+1]+f[i-1][p])%mod;
		for(int p=1;p<=K;p++){
			f[i][p]=s[i][p];
			for(int j=1;j<i;j++) f[i][p]=(f[i][p]+s[j][p+1]*c[i-1][j-1]%mod*f[i-j][p])%mod;
		}
	}
	printf("%lld",f[n][1]%mod);
	return 0;
}

Measured memory_bytes: 4480
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
l=abs(a-b)
if l==0:
    print('YES')
else:
    if w>=v:
        print('NO')
    else:
        if l<=t*(v-w):
            print('YES')
        else:
            print('NO')

Measured memory_bytes: 9072
A, B, C, D = gets.split('').map(&:to_i)
op = Array.new(3)
(1 << 3).times do |i|
  3.times do |j|
    if i >> j & 1 == 1
      op[j] = "+"
    elsif i >> j & 1 == 0
      op[j] = "-"
    end
  end
  if eval("#{A}#{op[0]}#{B}#{op[1]}#{C}#{op[2]}#{D}==7")
    puts "#{A}#{op[0]}#{B}#{op[1]}#{C}#{op[2]}#{D}=7"
    exit
  end
end

Measured memory_bytes: 1788
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  ll x,y;
  cin >> x >> y;

  if(abs(x-y)<=1){
    cout << "Brown" << endl;
  } else {
    cout << "Alice" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#include <cstdio>
#include <tuple>
#include <string>
#include <vector> 
#include <set>
#include <string.h>
#include <map>
#include <cmath>
#include <deque>
using ll = long long;
using Graph = vector<vector<int>>;
#include <queue>
#include <stack>


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

int main(){

    int a,b,k;
    cin >> a >> b >> k;

    int n = min(a,b);
    int c = gcd(max(a,b),n);
    vector<int> num;
    for(int i = 1;i <= c;i++){

        if(a % i == 0 && b % i == 0){
            
            num.push_back(i);
            
        }

    }

    cout << num[num.size()-k] << endl;
    return 0;
}

Measured memory_bytes: 256
H = int(input().rstrip())
Ai = [int(i) for i in input().rstrip().split()]

def maxHeapify(A, i):
    #สููตร heap หาตำแหน่งตัวซ้ายกับขวา
    l = 2*i
    r = 2*i+1
    #เทียบ 2 ตัวตามตำแหน่ง
    if l <= H and Ai[l-1] > Ai[i-1]:
        largest = l
    else:
        largest = i
    if r <= H and A[r-1] > A[largest-1]:
        largest = r
    #สลับข้างตัวที่มากกว่า
    if largest != i:
        Ai[i-1], Ai[largest-1] = Ai[largest-1], Ai[i-1]
        #เรีียกอีกรอบ
        #ทำจนกว่า max สุดจะอยู่บนแล้ว เอาnodeสุดท้ายของtreeเข้ามา swap แทน
        #จากนั้น remove maxออกไปเก็บ 
        maxHeapify(A, largest)

def buildMaxHeap(A):
    #ตั้งแต่ตำแหน่ง กลาง ถึง 0 เรียงด้านซ้ายก่อน
    for i in range(H//2,0,-1):
        maxHeapify(A, i)

buildMaxHeap(Ai)
for a in Ai:
    print(" "+str(a),end="")
print()



Measured memory_bytes: 63972
const numberList = require('fs').readFileSync('/dev/stdin','utf8').trim().split('\n')

var h = numberList[1].split(' ').map(e => parseInt(e))

var max = 0
var length = 0
for(var i=0;i<h.length - 1;i++) {
  if(h[i] >= h[i+1]) {
    length += 1
  } else {
    if(max < length) {
      max = length
    }
    length = 0
  }
}

if(max < length) {
  max = length
}

console.log(max)


Measured memory_bytes: 21064
n,m = map(int,input().split())
f = [[] for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    
    f[a].append(b)
    f[b].append(a)
    
import collections
q = collections.deque()

for i in range(n):
    for j in f[i]:
        q.append(j)
        
    while q:
        p = q.popleft()
        
        if p != i:
            f[i] += f[p]

            for k in f[p]:
                q.append(k)

            f[p] = []
        
    f[i] = sorted(set(f[i]))
            
ans = 1

for i in f:
    res = len(i)
    ans = max(ans,res)
    
print(ans)


Measured memory_bytes: 58676
/**
 *  Area Separation (Problem D, Practice Contest for Japan Domestic, 2005-06-19)
 *  by Kenji Inoue, 2007-01-07
 **/

#include <iostream>
#include <complex>
#include <vector>

using namespace std;

typedef complex<double> P;
#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )

P s[100], e[100];

double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

int main() {
  int n;
  while (cin >> n, n) {
    for (int i=0; i<n; i++) {
      cin >> s[i].real() >> s[i].imag();
      cin >> e[i].real() >> e[i].imag();
    }

    int ans = 1;
    for (int i=0; i<n; i++) {
      vector<P> isp; // intersection points found
      int cnt = 0;
      for (int j=0; j<i; j++) {
        P iv = e[i] - s[i];
        P jv = e[j] - s[j];
        // check if parallel
        if (abs(cross(iv, jv)) < EPS) { continue; }

        // calculate the intersection point
        P p = s[i] + iv * cross(jv, s[j]-s[i]) / cross(jv, iv);
        if (abs(p.real()) > 100.0 - EPS) { continue; }
        if (abs(p.imag()) > 100.0 - EPS) { continue; }

        bool duplicate = false;
        for (int k=0; k<isp.size(); k++) {
          if (EQV(p, isp[k])) {
            duplicate = true;
            break;
          }
        }
        if (!duplicate) {
          cnt++;
          isp.push_back(p);
        }
      }
      ans += cnt + 1;
    }

    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 968
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
 
using namespace std;
 
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=1e9+7;

int main()
{
    ll k;
    cin >> k;
    string s;
    cin >> s;
    if(s.length()>k){
        rep(i,k){
            cout << s[i];
        }
        cout << "..." << endl;
        return 0;
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define li          long
#define ll          long long
#define ull         unsigned long long
#define ff          first
#define ss          second
#define pii         pair<int,int>
#define pli         pair<li,li>
#define pll         pair<ll,ll>
#define pb          push_back
#define fo(i,k,n)   for(int i = k;i<n; i++)
#define ro(i,k,n)   for(int i = k; i>=n; i--)
#define tc          int t;cin>>t;while(t--)
#define all(v)      v.begin(),v.end()
#define inf         INT_MAX
#define ninf        INT_MIN
#define W(x)        cout<<x<<endl
#define WW(x,y)     cout<<x<<' '<<y<<endl;
#define in(x)       cin>>x
#define vi          vector<int>
#define vll         vector<long long>
#define vpi         vector<pair<int>>
#define vpll        vector<pair<long long>>
#define vvi         vector<vector<int>>
#define vvll        vector<vector<long long>>
#define vvpi        vector<vector<pair<int,int>>>
#define vvpll       vector<vector<pair<long long>>>
const ll mod1 = 99844353;
const ll mod2 = 1e9+7;
template <class T>
using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
} 

template<class T>
T power(T a,T b){
    T res = (T)1;
    while(b>0){
        if(b&1)res = res*a;
        b>>=1;
        a*=a;
    }
    return res;
}

void solve(){
    int ans = -1;
    for(int i = 1; i<=5; i++){
        int x;
        cin>>x;
        if(x == 0)ans = i;
    }
    cout<<ans;
}

signed main(){
    fastio();
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 3648
import numpy as np


A,B,M  = [int(i) for i in input().split()]

a = [int(i) for i in input().split()]

b = [int(i) for i in input().split()]

order = np.ones([M,3])

for i in range(M):
    order[i,0],order[i,1],order[i,2] = [int(j) for j in input().split()]
    
dis_pri = float('inf')
# discount
for i in range(M):
    if dis_pri > (a[int(order[i,0])-1] + b[int(order[i,1])-1] - order[i,2]):
        dis_pri = int(a[int(order[i,0])-1] + b[int(order[i,1])-1] - order[i,2])
        


        
sim_pri = int(min(a) + min(b))
ans = min(sim_pri, dis_pri)
              
print(ans)

Measured memory_bytes: 27512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rep(i,n) for (int i=0; i<(n); i++)
#define reps(i,s,n) for (int i=(s); i<(n); i++)
#define rep1(i,n) for (int i=1; i<=(n); i++)
#define repr(i,s,n) for (int i=(s)-1; i>=(n); i--)
#define print(a) cout << (a) << endl
#define all(v) v.begin(), v.end()
#define rsort(v) sort(v.rbegin(), v.rend())
typedef tuple<ll,ll,ll> road;


int main() {
  int N, Q;
  ll s, t, x, d;
  cin >> N >> Q;
  vector<road> r;
  rep(i,N) {
    cin >> s >> t >> x;
    r.push_back(make_tuple(s-x, t-x, x));
  }
  rsort(r);
  set<pair<ll,ll>> u; multiset<ll> p;
  rep(i,Q) {
    cin >> d;
    while (!r.empty()) {
      if (get<0>(r.back())<=d) {
        auto e = r.back();
        r.pop_back();
        u.insert(make_pair(get<1>(e), get<2>(e)));
        p.insert(get<2>(e));
      }
      else
        break;
    }
    while (!u.empty()) {
      if (u.begin()->first<=d) {
        auto it = p.find(u.begin()->second);
        p.erase(it);
        u.erase(u.begin());
      } else
        break;
    }
    if (p.empty()) {
      print(-1);
    } else {
      print(*(p.begin()));
    }
  }
  return 0;
}

Measured memory_bytes: 29752
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> cnt(n);
  for (int i = 0; i < k; ++i) {
    int d;
    cin >> d;
    for (int j = 0; j < d; ++j) {
      int a;
      cin >> a;
      a--;
      cnt[a]++;
    }
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (cnt[i] == 0) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin >> a >> b;
  if (a>=13){
    cout << b << endl;
  }
  else if (a>=6){
    cout << b/2 << endl;
  }
  else {
    cout << 0 << endl;
  }
}

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

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

  int h, w, d, idx = 0, a;
  int dp[90001];
  fill(dp, dp + 90001, 0);

  pair<int, int> p[90001];

  cin >> h >> w >> d;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      cin >> a;
      p[a - 1] = { i, j };
    }
  }

  for (int i = d; i < h * w; ++i) {
    dp[i] = dp[i - d] + abs(p[i].first - p[i - d].first) + abs(p[i].second - p[i - d].second);
  }

  int q;

  cin >> q;

  for (int i = 0; i < q; ++i) {
    int l, r;

    cin >> l >> r;

    cout << dp[r - 1] - dp[l - 1] << endl;
  }

  return 0;
}

Measured memory_bytes: 2176
#include <iostream>
using namespace std;
string s;
int main(void){
    cin>>s;
    for(int i=0;i<s.size();i+=2){
        if(s[i]=='L'){
            cout<<"No"<<endl;
            return 0;
        }
    }
    for(int i=1;i<s.size();i+=2){
        if(s[i]=='R'){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3


def solve(n, u, ts):
    res = 0
    end = 0
    for t in ts:
        res += min(u - end + t, u)
        end = u + t
    return res


def main():
    n, u = (int(x) for x in input().split())
    ts = [int(x) for x in input().split()]
    print(solve(n, u, ts))


if __name__ == '__main__':
    main()


Measured memory_bytes: 25200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int INT_INF = 1e9;
const ll MOD = 1e9 + 7;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 0; i <= n; i++)
#define rrep(i,n) for(int i=n;i>0;i--)
#define RREP(i,n) for(int i=n;i>=0;i--)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
using fint64 = int_fast64_t;
vector<int> edge[100005];
int dp[100005];
int dfs(int i){
    if(dp[i]>0)return dp[i];
    if(edge[i].size()!=0){
        int res=-INT_INF;
        rep(k,edge[i].size()){
            int s=edge[i][k];
            res=max({dfs(s)+1,res});
        }
        return dp[i]=res;
    }
}

int main() { 
	int n,m;cin>>n>>m;
    rep(i,m){
        int x,y;cin>>x>>y;
        edge[x].push_back(y);
    }
    rep(i,100005) dp[i]=-INT_INF;
    dp[0]=0;
    dp[1]=0;
    int ans=-INT_INF;
    for(int i=1;i<=n;i++) ans=max(ans,dfs(i));
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 8192
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

typedef pair<int,int> P;

int main(){
  int L,N,M,X;
  int se[110],e[110],ss[110],s[110];
  int sec[1010],dp[110][1010];
  string dummy;

  while(cin >> L >> N >> M >> X, L||N||M||X){
    for(int i=0;i<N;i++)cin >> dummy >> se[i] >> ss[i];
    for(int i=0;i<M;i++)cin >> dummy >> e[i] >> s[i];
    
    se[N] = ss[N] = 0;
    vector<P> v;
    
    int Min = 10000;
    for(int i=0;i<N;i++){
      Min = min(Min,se[i]);
      for(int j=i+1;j<=N;j++)
	v.push_back(P(se[i]+se[j],ss[i]+ss[j]));
    }
    sort(v.begin(),v.end());

    int Max = 0,pos = 0;
    for(int i=0;i<=L;i++){
      while(pos<v.size() && v[pos].first <= i)Max = max(Max,v[pos++].second);
      sec[i] = Max;
      for(int j=0;j<=M;j++)dp[j][i] = -1;
    }

    dp[0][0] = 0;
    for(int i=0;i<M;i++)
      for(int j=L-e[i];j>=0;j--)
	for(int k=0;k<=M;k++)
	  if(0<=dp[k][j])dp[k+1][j+e[i]] = max(dp[k+1][j+e[i]],dp[k][j] + s[i]);
    
    int ans = 0;
    for(int i=0;i<=L-Min;i++)
      for(int j=X;j<=M;j++)ans = max(ans,dp[j][i] + sec[L-i]);
    cout << ans << endl;
  }
}

Measured memory_bytes: 1440
#include <bits/stdc++.h>
 
#define int          long long
#define pb          push_back
#define pii         pair<int,int> 
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007 
#define mem(x)      memset(x,0,sizeof(x));
#define what_is(x)  cout << #x << " is " << x << flush << endl;
#define rep(i,a,b)  for(int i=a;i<b;i++)
 
using namespace std;
const int maxn = 100010;
int n,w;
int val[maxn], wt[maxn];
void solve(){
	cin>>n>>w;
	int sum = 0;
	rep(i,0,n)
		cin>>wt[i]>>val[i], sum+=val[i];
	vector<int> dp(sum+1, INT_MAX);
dp[0] = 0;
	for(int i = 0; i<n; i++)
	{
		for(int j = sum - val[i]; j>=0; j--)
			dp[j+val[i]] = min(dp[j+val[i]], dp[j] + wt[i]);
	}
	int ans = -INT_MAX;
	rep(i, 0, sum+1)
	{
		if(dp[i]<=w)
			ans = max(ans, i);
	}
	cout<<ans;




}
 
signed main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
     //cin>>t;
 
    while(t--)
        solve();
    
    return 0;
}

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

int main() {

    ll n;
    cin >> n;

    ll ans = 0;
    ans += (n / 500) * 1000;
    n %= 500;
    ans += (n / 5) * 5;
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

bool dfs(vector<vector<int>> &tr, int parent, int cur, vector<int> &path) {
    if (cur == tr.size() - 1) {
        path.push_back(cur);
        return true;
    }
    for (auto nxt : tr[cur]) {
        if (nxt == parent) continue;
        if (dfs(tr, cur, nxt, path)) {
            path.push_back(cur);
            return true;
        }
    }
    return false;
}

void dfs2(vector<vector<int>> &tr, int cur, vector<int> &col) {
    for (auto nxt : tr[cur]) {
        if (col[nxt]) continue;
        col[nxt] = col[cur];
        dfs2(tr, nxt, col);
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> tr(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    vector<int> path;
    dfs(tr, -1, 0, path);
    vector<int> col(n);
    for (int i = 0; i < path.size() / 2; ++i) {
        col[path[i]] = 1;
    }
    for (int i = path.size() / 2; i < path.size(); ++i) {
        col[path[i]] = 2;
    }
    for (auto r : path) {
        dfs2(tr, r, col);
    }
    array<int, 2> cnts;
    for (auto c : col) {
        ++cnts[c - 1];
    }
    cout << (cnts[0] >= cnts[1] ? "Snuke" : "Fennec") << endl;
    return 0;
}


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

using namespace std;

#define MAX 2 * 100000 + 5


int main(void) {
	int N;
	int count = 0;

	double D, d;
	double x, y;

	cin >> N >> D;

	//cout << D << endl;

	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		if (fabs(x) > 10000 && fabs(y) > 10000) {
			x /= 10000;
			y /= 10000;
			//d = sqrt(x * x + y * y);
			d = sqrt(x * x + y * y);
		//	cout << d <<"," << D <<endl;
			if (d <= (D/ 10000)) {
				count++;
			}
		}
		else if((int)x == 0 && (int)y == 0) {
			count++;
		}
		else {
			d = sqrt(x * x + y * y);
			//cout << d << endl;
			if (d <= D) {
				count++;
			}
		}
	}
	cout << count << endl;



	return 0;
}


Measured memory_bytes: 3160
#include <stdio.h>

int check(char c){
    switch(c){
        case 'y':
        case 'u':
        case 'i':
        case 'o':
        case 'p':
        case 'h':
        case 'j':
        case 'k':
        case 'l':
        case 'n':
        case 'm':
            return 1;
        default:
            return 0;
    }
}

int main(void){
    char line[34];
    int count,i;
    while(scanf("%s",line),line[0]!='#'){
        count=0;
        for(i=0;line[i+1];i++){
            if(check(line[i])!=check(line[i+1])) count++;
        }
        printf("%d\n",count);
    }
    return 0;
}

Measured memory_bytes: 540
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
  int a, b;

  cin >> a >> b;

  int n, x;

  n = b - a - 1;

  x = n * (n + 1) / 2 - a;
  //cout << n << endl;

  cout << x << endl;


  return 0;

}


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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    string S;
    cin >> S;
    ll ans = 0;
    for (int i = 0; i < 6; i++) {
        if(S[i] == '1'){
            ans++;
        }
    }
    cout << ans << endl;
}

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

using namespace std;

int n,m;
vector<vector<int> > edge;
int ise[100000];
int ans[100000];

void dfs(int p){
    vector<int> s;
    for(int i = 0;i < edge[p].size();i++){
        ise[edge[p][i]]--;
        if(ise[edge[p][i]] == 0) s.push_back(edge[p][i]);
    }
    for(int i = 0;i < s.size();i++){
        ans[s[i]] = p+1;
        dfs(s[i]);
    }
}

void solve(){
    int i,j;
    string str;
    cin >> n >> m;
    edge.resize(n);
    for(i = 0;i < n-1+m;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        edge[a].push_back(b);
        ise[b]++;
    }
    for(i = 0;i < n;i++){
        if(ise[i] == 0){
            ans[i] = 0;
            dfs(i);
            break;
        }
    }
    for(i = 0;i < n;i++)
    cout << ans[i] << endl;
}

int main(){
    solve();
}


Measured memory_bytes: 16384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
    int n,d;
    ll ans=0;
    cin>>n>>d;

    vector<vector<int>> v(n,vector<int>(d));
    for(int i=0;i < n;i++)
    {
        for(int j=0;j < d;j++)
        {
            cin>>v.at(i).at(j);
        }
    }

    for(int i=0;i < n;i++)
    {
        for(int j=i+1;j < n;j++)
        {
            double dis=0;
            for(int k=0;k < d;k++)
            {
                dis+=(v[i][k]-v[j][k])*(v[i][k]-v[j][k]);
            }

            bool flag=false;
            for(int k=-1000;k <= 1000;k++)
            {
                if(sqrt(dis)==k){
                    flag=true;
                    break;
                }
            }
            if(flag)ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()

{

    int a,b;

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

    if(a<b){

        printf("a < b\n");

    }

    else if(a>b){

        printf("a > b\n");

    }

    else{

        printf("a == b\n");

    }

    return 0;

}


Measured memory_bytes: 2076
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int main()
{
    ll H, W;
    cin >> H >> W;
    ll s = H * W;
    ll sa, sb, sc;
    ll s_max, s_min;
    for (int h = 1; h <= H - 1; ++h) {
        sa = h * W;
        // vertical
        sb = (H - h) * (W / 2);
        sc = (H - h) * (W - W / 2);
        s_max = max({ sa, sb, sc });
        s_min = min({ sa, sb, sc });
        s = min(s, s_max - s_min);

        // horizontal
        sb = ((H - h) / 2) * W;
        sc = ((H - h) - (H - h) / 2) * W;
        s_max = max({ sa, sb, sc });
        s_min = min({ sa, sb, sc });
        s = min(s, s_max - s_min);
    }

    for (int w = 1; w <= W - 1; ++w) {
        sa = w * H;
        // vertical
        sb = (W - w) * (H / 2);
        sc = (W - w) * (H - H / 2);
        s_max = max({ sa, sb, sc });
        s_min = min({ sa, sb, sc });
        s = min(s, s_max - s_min);

        // horizontal
        sb = ((W - w) / 2) * H;
        sc = ((W - w) - (W - w) / 2) * H;
        s_max = max({ sa, sb, sc });
        s_min = min({ sa, sb, sc });
        s = min(s, s_max - s_min);
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Set<Integer> s = new HashSet<>();
		for (int i = 0; i < n; i++) {
			s.add(sc.nextInt());
		}
		int q =sc.nextInt();
		List<Integer> t = new ArrayList<>();
		for (int i = 0; i < q; i++) {
			t.add(sc.nextInt());
		}
		int count = 0;
		for (int i = 0; i < q; i++) {
			int e = t.get(i);
			for (Integer j : s) {
				if (j.intValue() == e) {
					count++;
					break;
				}
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 40348
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
 
using namespace std;


int MOD=1000000007;

int main(void){
    double N,ans=0;
        cin >> N;
    double A[101];
    for(int i=0; i<N; i++){
        cin >> A[i];
        ans+=(1/A[i]);
    }
    cout << 1/ans << endl;

    


    
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws Exception{
		int num = 998244353;

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		long t = Long.parseLong(bf.readLine());
 		long j = 100;
 		int count = 0;
 		while(j < t){
 			count++;
 			j = j+j/100;
 		}
 		out.println(count);
 		out.close();
 	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	




Measured memory_bytes: 25408
A, B, C, X, Y = map(int, input().split())
min_price = A * X + B * Y
AB = 2 * C
for i in range(10**5 + 1):
    p = i * AB + max(0, X - i) * A + max(0, Y - i)  * B   
    if p < min_price:
        min_price = p           

print(min_price)

Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let m: usize = read();
    let mut s = vec![vec![]; m];
    for i in 0..m {
        let k: usize = read();
        for _ in 0..k {
            // sにはk個の各スイッチの1～Nの番号
            let a = read::<usize>() - 1;
            s[i].push(a);
        }
    }
    let p: Vec<usize> = (0..m).map(|_| read()).collect();

    let mut res = 0;
    for bit in 0..1 << n {
        let mut ok = true;
        for (i, switch) in s.iter().enumerate() {
            let mut con = 0;
            for &i in switch.iter() {
                if bit & 1 << i == 1<<i {
                    con += 1;
                }
            }
            if con % 2 != p[i] {
                ok = false;
                break;
            }
        }
        if ok {
            res += 1;
        }
    }
    println!("{}", res);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;
const ull MOD = 998244353;
#ifdef LOCAL
#include "../../pp.hpp"
#define debug pp::debug
#else
#define debug(args...)
#endif

const int NMAX = 301*301*300 + 301*300 + 300 + 1;
double dp[NMAX];
int n;

typedef array<double, 3> State;

int to_int(const State& st) {
    return 301*301*st[0] + 301*st[1] + st[2];
}

double solve(State& st) {
    if (st[0] == 1 && st[1] == 0 && st[2] == 0) return n;

    int st_int = to_int(st);
    if (dp[st_int] != -1.0) return dp[st_int];

    double n_nonzero = st[0] + st[1] + st[2];
    double ans = (double)n/n_nonzero;
    for (int i = 0; i < 3; ++i) {
        if (st[i] != 0) {
            st[i]--;
            if (i != 0) st[i-1]++;
            ans += ((st[i] + 1) / n_nonzero) * solve(st);
            st[i]++;
            if (i != 0) st[i-1]--;
        }
    }
    dp[st_int] = ans;
    return ans;
}

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

    cin >> n;
    State st = {0, 0, 0};
    for (int i = 0; i < n; ++i) {
        int a; cin >> a;
        st[a-1]++;
    }
    for (int i = 0; i < NMAX; ++i) dp[i] = -1.0;
    double ans = solve(st);
    cout << fixed << setprecision(10) << ans << '\n';
}


Measured memory_bytes: 213376
import sys
import functools
import collections
import operator


def resolve(in_):
    n = int(next(in_))
    s = next(in_).strip()

    c = collections.Counter()
    c[b'R'[0]] = 0
    c[b'G'[0]] = 0
    c[b'B'[0]] = 0
    c.update(s)
    ans = functools.reduce(operator.mul, c.values())
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            k = j * 2 - i
            if k - 1 >= n:
                break
            si = s[i - 1]
            sj = s[j - 1]
            sk = s[k - 1]
            if si != sj and sj != sk and sk != si:
                ans -= 1
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9540
use std::collections::BinaryHeap;
use std::cmp;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.read();
    let a: Vec<i64> = (0..(3 * n)).map(|_| sc.read()).collect();
    let mut prefix_sum = vec![0; 3 * n];
    let mut heap = BinaryHeap::new();
    for i in 0..n {
        heap.push(-a[i]);
        prefix_sum[i] = a[i];
        if i > 0 {
            prefix_sum[i] += prefix_sum[i - 1];
        }
    }

    for i in n..(3 * n) {
        let p = -heap.pop().unwrap();
        let s = cmp::max(p, a[i]);
        heap.push(-s);
        prefix_sum[i] = prefix_sum[i - 1] - p + s;
    }

    heap.clear();
    let mut suffix_sum = vec![0; 3 * n];
    for i in ((2 * n)..(3 * n)).rev() {
        heap.push(a[i]);
        suffix_sum[i] = a[i];
        if i < 3 * n - 1 {
            suffix_sum[i] += suffix_sum[i + 1];
        }
    }

    for i in (0..(2 * n)).rev() {
        let p = heap.pop().unwrap();
        let s = cmp::min(p, a[i]);
        heap.push(s);
        suffix_sum[i] = suffix_sum[i + 1] - p + s;
    }

    let mut max = std::i64::MIN;
    for i in n..(2 * n + 1) {
        let prefix = prefix_sum[i - 1];
        let suffix = suffix_sum[i];
        max = cmp::max(max, prefix - suffix);
    }
    println!("{}", max);
}

struct Scanner {
    ptr: usize,
    length: usize,
    buf: Vec<u8>,
    small_cache: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024] }
    }

    fn load(&mut self) {
        use std::io::Read;
        let mut s = std::io::stdin();
        self.length = s.read(&mut self.buf).unwrap();
    }

    fn byte(&mut self) -> u8 {
        if self.ptr >= self.length {
            self.ptr = 0;
            self.load();
            if self.length == 0 {
                self.buf[0] = b'\n';
                self.length = 1;
            }
        }

        self.ptr += 1;
        return self.buf[self.ptr - 1];
    }

    fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' }

    fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, {
        let mut b = self.byte();
        while Scanner::is_space(b) {
            b = self.byte();
        }

        for pos in 0..self.small_cache.len() {
            self.small_cache[pos] = b;
            b = self.byte();
            if Scanner::is_space(b) {
                return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]).parse().unwrap();
            }
        }

        let mut v = self.small_cache.clone();
        while !Scanner::is_space(b) {
            v.push(b);
            b = self.byte();
        }
        return String::from_utf8_lossy(&v).parse().unwrap();
    }
}



Measured memory_bytes: 16636
#include<bits/stdc++.h>
using namespace std;
string s;
char a[100010];
int main()
{
     cin>>s;
     int k=0;
     for(int i=0;i<s.size();i++)
     {
        if(s[i]!='B') a[++k]=s[i];
        else 
         {
            k--;
            if(k<0) k=0;
         }
     }
     for(int i=1;i<=k;i++)
        cout<<a[i];
     cout<<"\n";
 return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define _for(i,a,b) for(int i = (a);i<(b);i++)
#define endl  '\n'
#define inf 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;
const int MAX=1e6+7;
//ll a[MAX];
int main()
{
 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 	ll n;cin>>n;
 	for(ll i=0;i<=200;i++)
 	{
 		for(ll j=-200;j<=200;j++)
		 {
		 	if(pow(i,5)-pow(j,5)==n)
		 	{
				cout<<i<<" "<<j;
				return 0; 		
			 }
			 
		}	
	}
 	
 	
}

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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

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

  vector<ll> x(m);
  vector<ll> y(m);
  for (ll i = 0; i < m; ++i) {
    cin >> x[i] >> y[i];
    x[i]--; y[i]--;
  }

  vector<ll> box(n, 1);
  vector<bool> mark(n);
  mark[0] = true;
  for (ll i = 0; i < m; ++i) {
    auto xi = x[i];
    auto yi = y[i];
    box[xi]--;
    box[yi]++;
    if (mark[xi]) mark[yi] = true;
    if (box[xi] == 0) mark[xi] = false;
  }

  ll ans = 0;
  for (ll i = 0; i < n; ++i) {
    if (mark[i]) ++ans;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2560
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Threading.Tasks;
using System.Globalization;
namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamScanner scan = new StreamScanner(System.Console.OpenStandardInput());
            string s = scan.Scan();
            if (s == "AAA" || s=="BBB") { Console.WriteLine("No"); }
            else
            {
                Console.WriteLine("Yes");
            }

        }
    }
    public class StreamScanner
    {
        public StreamScanner(Stream stream) { str = stream; }
        private readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }
        private byte read()
        {
            if (isEof) throw new EndOfStreamException();
            if (ptr >= len)
            {
                ptr = 0;
                if ((len = str.Read(buf, 0, 1024)) <= 0)
                {
                    isEof = true;
                    return 0;
                }
            }
            return buf[ptr++];
        }
        public char Char()
        {
            byte b = 0;
            do b = read();
            while (b < 33 || 126 < b);
            return (char)b;
        }
        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        public long Long()
        {
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != '-' && (b < '0' || '9' < b));
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = ret * 10 + b - '0';
            }
        }
        public int Integer() { return (int)Long(); }
        public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
    public class UnionFind
    {
        public int[] data;

        public UnionFind(int size)
        {
            data = new int[size];
            for (int i = 0; i < size; i++) data[i] = -1;
        }

        public bool Unite(int x, int y)
        {
            x = Root(x);
            y = Root(y);

            if (x != y)
            {
                if (data[y] < data[x])
                {
                    var tmp = y;
                    y = x;
                    x = tmp;
                }
                data[x] += data[y];
                data[y] = x;
            }
            return x != y;
        }

        public bool IsSameGroup(int x, int y)
        {
            return Root(x) == Root(y);
        }

        public int Root(int x)
        {
            return data[x] < 0 ? x : data[x] = Root(data[x]);
        }
    }
}


Measured memory_bytes: 13140
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
using namespace std;

int H,W;
string S[2000];

int ans = 0;

void solve(){
	vector<vector<int>> memo_width(H,vector<int>(W,0));
	vector<vector<int>> memo_height(H,vector<int>(W,0));
	for(int h=0;h<H;h++){
		for(int w=0;w<W;w++){
			int light_number = 0;
			if(S[h][w]=='#') continue;

			//横方向について幅を調べる
			if(memo_width[h][w]==0){
				int edge_left,edge_right;
				for(int i=w;i<W;i++){
					if(S[h][i]=='.') edge_right = i;
					else break;
				}
				for(int i=w;i>=0;i--){
					if(S[h][i]=='.') edge_left = i;
					else break;
				}
				for(int i=edge_left;i<=edge_right;i++){
					memo_width[h][i] = edge_right - edge_left + 1;
				}
			}
			light_number+=memo_width[h][w];

			//縦方向について幅を調べる
			if(memo_height[h][w]==0){
				int edge_top,edge_bottom;
				for(int i=h;i<H;i++){
					if(S[i][w]=='.') edge_bottom = i;
					else break;
				}
				for(int i=h;i>=0;i--){
					if(S[i][w]=='.') edge_top = i;
					else break;
				}
				for(int i=edge_top;i<=edge_bottom;i++){
					memo_height[i][w] = edge_bottom - edge_top + 1;
				}
			}
			light_number+=memo_height[h][w];

			light_number--;
			if(light_number>ans) ans = light_number;
			//cout << "h,w=" << h << "," << w << " light_number=" << light_number << endl;
		}
	}
}
 
int main(){
	cin >> H >> W;
	for(int i=0;i<H;i++) cin >> S[i];
 
	solve();
 
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 35712
/*
    ThunderClap and Flash
    Raunaq Singh
*/
#include "bits/stdc++.h" 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
#define ThunderClap ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
#define debugg(something)   cout<<#something<<" - "<<something<<"\n";
#define vi vector
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define LB lower_bound
#define UB upper_bound
#define mp make_pair
#define pb push_back
#define in insert
#define s second
#define f first
#define pQueue priority_queue
#define maxElement *max_element
#define minElement *min_element
#define MAX 100000LL
#define mod 1000000007LL
#define inf 1000000000000000000LL
#define mI2 500000004LL
inline ll add(ll a, ll b){ return ((a%mod) + (b%mod))%mod;}
inline ll mul(ll a, ll b){ return ((a%mod) * (b%mod))%mod;}
inline ll sub(ll a, ll b){ return ((a%mod) - (b%mod) + mod)%mod;}

void Flash(){
    ll a, b, c, k;
    cin>>a>>b>>c>>k;
    while (b <= a) {
        b *= 2;
        --k;
    }
    //debugg(k);
    while (c <= b) {
        c *= 2;
        --k;
    }
    //debugg(k);
    //debugg(b);
    //debugg(c);
    if (k < 0) {
        cout<<"No\n";
    } else {
        cout<<"Yes\n";
    }
    
}

int main(int argc, char const *argv[]){ 
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
    #endif
    ThunderClap;
    ll t = 1;
    //cin>>t;
    for(ll i = 1; i <= t; i++){
        //cout<<"Case #"<<i<<": ";
        Flash();
    }
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
 
#define endl '\n'
#define loop(i, m, n) for (ll i = m; i < n; i++)
#define loope(i, m, n) for (ll i = m; i <= n; i++)
#define epool(i, m, n) for (ll i = m; i >= n; i--)
#define mod 1000000007
#define mod2 998244353
#define vi vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define empf emplace_front
#define empb emplace_back
#define ret(x) return cout << x,0;
#define all(v) v.begin(),v.end()
#define maxheap priority_queue<ll>
#define minheap priority_queue<ll,vector<ll>,greater<ll>>
const ll INF=1e18;
const double PI=4*atan(1);

#define SpeedForce                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;

ll mpow(ll base,ll exp,ll M);
ll POW(ll base,ll exp);
ll gcd(ll a,ll b);
ll lcm(ll a,ll b);
ll modInverse(ll n);
ll nCr(ll n, ll r);

void solve(){
    ll n;
    cin >> n;
    ll ans=0;
    if(n<=599) ans=8;
    else if(n<=799) ans=7;
    else if(n<=999) ans=6;
    else if(n<=1199) ans=5;
    else if(n<=1399) ans=4;
    else if(n<=1599) ans=3;
    else if(n<=1799) ans=2;
    else if(n<=1999) ans=1;
    cout << ans << endl;

}

int32_t main(){
    SpeedForce
    ll i = 0,j = 0;

    int t;
    t=1;
    //cin >> t;
    //ll cnt=1;
    while (t--){
        //cout << "Case #" << cnt << ": ";
        //cout << fixed << setprecision(10);
        solve();
        //cout << endl;
        //cnt++;
    }
}

ll POW(ll base,ll exp){
    ll result = 1;
    while (exp > 0){
        if (exp & 1)
            result = ((ll)result * base);
        base = ((ll)base * base);
        exp >>= 1;
    }
    return result;
}

ll mpow(ll base, ll exp,ll M){
    base %= M;
    ll result = 1;
    while (exp > 0){
        if (exp & 1)
            result = ((ll)result * base) % M;
        base = ((ll)base * base) % M;
        exp >>= 1;
    }
    return result%M;
}

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

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

ll modInverse(ll n) { 
    return mpow(n, mod-2,mod); 
}
 
ll nCr(ll n, ll r){ 
   if (r==0) 
      return 1; 
    ll fac[n+1]; 
    fac[0] = 1; 
    for (int i=1 ; i<=n; i++) 
        fac[i] = (fac[i-1]*i)%mod; 
    return ((fac[n]* modInverse(fac[r]) % mod * 
            modInverse(fac[n-r]) % mod)%mod)%mod; 
}

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

#include <boost/multiprecision/cpp_dec_float.hpp>

using namespace std;
namespace mp = boost::multiprecision;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);

  // int64_t a, ans;
  // mp::cpp_dec_float_50 b;
  // cin >> a >> b;

  // b *= a;
  // ans = (int64_t)b;

  int64_t a, ans;
  long double b;
  cin >> a >> b;
  // cerr << (int)(b * 100) << '\n';
  // cerr << floor(b * 100) << '\n';
  // cerr << round(b * 100) << '\n';
  ans = (a * (int64_t)round(b * 100)) / 100;

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 3756
// Battle


// AC
#include <bits/stdc++.h>
using namespace std;

int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	
	bool taka=false;
	while(a>0 && c>0){
		c -= b;
		if(c<=0){
			taka=true;
			break;
		}
		
		a -= d;
		if(a<=0){
			taka=false;
			break;
		}
	}
	if(taka) cout << "Yes";
	else cout << "No";
}


Measured memory_bytes: 3632