stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

typedef vector<int> vi;

#define TAM 100100



ll A[TAM];

vi G[TAM];



bool ok ( int i, int pi = -1 ) {

  if ( G[i].size() == 1 )

    return true;



  ll sum = 0, maxAj = 0;

  for ( int j : G[i] )

    if ( j != pi ) {

      if ( !ok(j, i) )

        return false;

      sum += A[j];

      maxAj = max ( maxAj, A[j] );

    }



  // x + A[i] = sum

  ll x = sum - A[i];



  if ( x < 0 || maxAj > A[i] )

    return false;



  A[i] -= x;

  return A[i] >= 0;

}



int main() {

  int n;

  scanf ( "%d", &n );

  for ( int i = 1, tmp; i <= n; ++i ) {

    scanf ( "%d", &tmp );

    A[i] = tmp;

  }

  for ( int edges = n-1, a, b; edges--; ) {

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

    G[a].pb ( b );

    G[b].pb ( a );

  }



  if ( n == 2 ) {

    puts ( A[1] == A[2] ? "YES" : "NO" );

    return 0;

  }



  int root = 1;

  while ( G[root].size() == 1 ) root++;



  if ( ok(root) && A[root] == 0 ) puts ("YES");

  else puts("NO");

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 18.51399165022443x):
#include <cstdio>

#include <algorithm>

#define int long long

using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5;

int n;

int head[MAXN] , to[MAXN << 1] , nxt[MAXN << 1] , cnt , ans , du[MAXN << 1];

LL f[MAXN] , a[MAXN];

void add(int u , int v) {nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;}

void dfs(int x , int fa) {

	LL _sum = 0 , mx = 0;

	for (int i = head[x]; i; i = nxt[i]) {

		if(to[i] == fa) continue;

		dfs(to[i] , x);

		if(ans) return;

		mx = max(mx , f[to[i]]);

		_sum += f[to[i]];

	}

	if(!_sum) {

		f[x] = a[x];

		return;

	}

	f[x] = 2ll * a[x] - _sum;

	if(f[x] < 0 || f[x] > a[x] || mx - f[x] > _sum - mx || a[x] < mx) {

		printf("NO");

		exit(0);

	}

}

signed main() {

	scanf("%lld" , &n);

	for (int i = 1; i <= n; ++i) scanf("%lld" , &a[i]);

	if (n == 2) return puts(a[1] == a[2] ? "YES" : "NO"), 0;

	int root = 0;

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

		int u , v;

		scanf("%lld %lld" , &u , &v);

		du[u] ++;du[v] ++;

		add(u , v);add(v , u);

		if(du[u] > 1) root = u;

		if(du[v] > 1) root = v;

	}

	dfs(root , 0);

	if(f[root]) printf("NO");

	else printf("YES");

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;  



const int maxn = 1e5 + 10;



int n;

vector<int> e[maxn];

long long a[maxn];

bool dfs(int x, int fa) {

	if(e[x].size() == 1) return true;

	long long sum = 0, mx = 0;

	for(auto &it : e[x]) {

		int v = it;

		if(v == fa) continue;

		if(!dfs(v, x)) return false;

		sum += a[v];

		mx = max(mx, a[v]);

	}

	mx = min(sum - mx, sum / 2);

	long long tmp = sum - a[x];

	if(tmp < 0 || tmp > mx) return false;

	a[x] -= tmp;

	if(x == fa) return a[x] == 0;

	return true;

}

int main() {

	scanf("%d", &n);

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

		scanf("%lld", &a[i]);

	}

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

		int x, y;

		scanf("%d%d", &x, &y);

		e[x].push_back(y);

		e[y].push_back(x);

	}

	if(n == 2) {

		a[1] == a[2] ? printf("YES\n") : printf("NO\n");

		return 0;

	}

	int pos = -1;

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

		if(e[i].size() != 1) {

			pos = i;

			break;

		}

	}

	dfs(pos, pos) ? printf("YES\n") : printf("NO\n");

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 18.520813127677204x):
#include <cstdio>

#include <algorithm>

#define int long long

using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5;

int n;

int head[MAXN] , to[MAXN << 1] , nxt[MAXN << 1] , cnt , ans , du[MAXN << 1];

LL f[MAXN] , a[MAXN];

void add(int u , int v) {nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;}

void dfs(int x , int fa) {

	LL _sum = 0 , mx = 0;

	for (int i = head[x]; i; i = nxt[i]) {

		if(to[i] == fa) continue;

		dfs(to[i] , x);

		if(ans) return;

		mx = max(mx , f[to[i]]);

		_sum += f[to[i]];

	}

	if(!_sum) {

		f[x] = a[x];

		return;

	}

	f[x] = 2ll * a[x] - _sum;

	if(f[x] < 0 || f[x] > a[x] || mx - f[x] > _sum - mx || a[x] < mx) {

		printf("NO");

		exit(0);

	}

}

signed main() {

	scanf("%lld" , &n);

	for (int i = 1; i <= n; ++i) scanf("%lld" , &a[i]);

	if (n == 2) return puts(a[1] == a[2] ? "YES" : "NO"), 0;

	int root = 0;

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

		int u , v;

		scanf("%lld %lld" , &u , &v);

		du[u] ++;du[v] ++;

		add(u , v);add(v , u);

		if(du[u] > 1) root = u;

		if(du[v] > 1) root = v;

	}

	dfs(root , 0);

	if(f[root]) printf("NO");

	else printf("YES");

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



typedef long long LL;

const int Maxn = 111111;

struct Edge {

	int v, id;

	Edge *nxt;

} pool[Maxn*2], *tree[Maxn], *tail = pool;

inline void addedge(const int &u, const int &v, const int &id) {

	tail->v = v, tail->id = id;

	tail->nxt = tree[u], tree[u] = tail++;

}



int n, a[Maxn], w[Maxn];

bool isleaf[Maxn];



void dfs(int u, int fa, int lastid) {

	w[lastid] = a[u];

	isleaf[u] = true;

	for (Edge *p = tree[u]; p; p = p->nxt) {

		if (p->v != fa) {

			isleaf[u] = false;

			dfs(p->v, u, p->id);

			w[lastid] -= w[p->id];

		}

	}

	if (!isleaf[u]) {

		w[lastid] += a[u];

	}

}

void solve() {

	if (n == 2) {

		if (a[1] == a[2]) {

			puts("YES");

		} else {

			puts("NO");

		}

		return;

	}

	for (int i = 1, cnum; i <= n; ++i) {

		cnum = 0;

		for (Edge *p = tree[i]; p; p = p->nxt) {

			++cnum;

		}

		if (cnum > 1) {

			dfs(i, 0, 0);

			break;

		}

	}

	if (w[0] != 0) {

		puts("NO");

		return;

	}

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

		if (w[i] < 0) {

			puts("NO");

			return;

		}

	}

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

		if (!isleaf[i]) {

			LL tot = 0;

			for (Edge *p = tree[i]; p; p = p->nxt) {

				tot += w[p->id];

			}

			for (Edge *p = tree[i]; p; p = p->nxt) {

				if (w[p->id] > tot/2) {

					puts("NO");

					return;

				}

			}

		}

	}

	puts("YES");

}



int main() {

	scanf("%d", &n);

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

		scanf("%d", &a[i]);

	}

	for (int i = 1, x, y; i < n; ++i) {

		scanf("%d%d", &x, &y);

		addedge(x, y, i), addedge(y, x, i);

	}

	solve();

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.185489568135898x):
#include <cstdio>

#include <algorithm>

#define int long long

using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5;

int n;

int head[MAXN] , to[MAXN << 1] , nxt[MAXN << 1] , cnt , ans , du[MAXN << 1];

LL f[MAXN] , a[MAXN];

void add(int u , int v) {nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;}

void dfs(int x , int fa) {

	LL _sum = 0 , mx = 0;

	for (int i = head[x]; i; i = nxt[i]) {

		if(to[i] == fa) continue;

		dfs(to[i] , x);

		if(ans) return;

		mx = max(mx , f[to[i]]);

		_sum += f[to[i]];

	}

	if(!_sum) {

		f[x] = a[x];

		return;

	}

	f[x] = 2ll * a[x] - _sum;

	if(f[x] < 0 || f[x] > a[x] || mx - f[x] > _sum - mx || a[x] < mx) {

		printf("NO");

		exit(0);

	}

}

signed main() {

	scanf("%lld" , &n);

	for (int i = 1; i <= n; ++i) scanf("%lld" , &a[i]);

	if (n == 2) return puts(a[1] == a[2] ? "YES" : "NO"), 0;

	int root = 0;

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

		int u , v;

		scanf("%lld %lld" , &u , &v);

		du[u] ++;du[v] ++;

		add(u , v);add(v , u);

		if(du[u] > 1) root = u;

		if(du[v] > 1) root = v;

	}

	dfs(root , 0);

	if(f[root]) printf("NO");

	else printf("YES");

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstdlib>

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN=100005;



void NoSolution()

{

	puts("NO");

	fclose(stdin);

	fclose(stdout);

	exit(0);

}



int n,A[MAXN];

vector<int> adj[MAXN];



int dfs(int u,int fa=0)

{

	if(adj[u].size()==1U)

		return A[u];

	long long sum=0;

	int tmp=0,mx=0;

	for(int i=0;i<(int)adj[u].size();i++)

	{

		int v=adj[u][i];

		if(v==fa)

			continue;

		tmp=dfs(v,u);

		mx=max(mx,tmp);

		sum+=tmp;

	}

	if(fa==0)

	{

		if(sum%2==1||mx>sum/2||A[u]!=sum/2)

			NoSolution();

		return 0;

	}

	long long delta=sum-A[u];

	if(A[u]<delta||sum<A[u]||sum-mx<delta)

		NoSolution();

	return A[u]-delta;

}



int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%d",&A[i]);

	if(n==2)

	{

		if(A[1]==A[2])

			puts("YES");

		else

			puts("NO");

		return 0;

	}

	for(int i=1;i<n;i++)

	{

		int a,b;

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

		adj[a].push_back(b);

		adj[b].push_back(a);

	}

	for(int i=1;i<=n;i++)

		if(adj[i].size()>1U)

		{

			dfs(i);

			break;

		}

	puts("YES");

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 18.136661665777932x):
#include <cstdio>

#include <algorithm>

#define int long long

using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5;

int n;

int head[MAXN] , to[MAXN << 1] , nxt[MAXN << 1] , cnt , ans , du[MAXN << 1];

LL f[MAXN] , a[MAXN];

void add(int u , int v) {nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;}

void dfs(int x , int fa) {

	LL _sum = 0 , mx = 0;

	for (int i = head[x]; i; i = nxt[i]) {

		if(to[i] == fa) continue;

		dfs(to[i] , x);

		if(ans) return;

		mx = max(mx , f[to[i]]);

		_sum += f[to[i]];

	}

	if(!_sum) {

		f[x] = a[x];

		return;

	}

	f[x] = 2ll * a[x] - _sum;

	if(f[x] < 0 || f[x] > a[x] || mx - f[x] > _sum - mx || a[x] < mx) {

		printf("NO");

		exit(0);

	}

}

signed main() {

	scanf("%lld" , &n);

	for (int i = 1; i <= n; ++i) scanf("%lld" , &a[i]);

	if (n == 2) return puts(a[1] == a[2] ? "YES" : "NO"), 0;

	int root = 0;

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

		int u , v;

		scanf("%lld %lld" , &u , &v);

		du[u] ++;du[v] ++;

		add(u , v);add(v , u);

		if(du[u] > 1) root = u;

		if(du[v] > 1) root = v;

	}

	dfs(root , 0);

	if(f[root]) printf("NO");

	else printf("YES");

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

typedef long long ll;

#define pb push_back

#define mp make_pair

#define fi first

#define se second

using namespace std;

ll n,i,a[101010],D[101010],R,ta,tb;

vector<ll> v[101010];

ll dfs(ll aa,ll bb)

{

	if(D[aa]==1)

		return a[aa];

	ll ii;

	vector<ll> isi;

	for(ii=0;ii<v[aa].size();ii++)

	{

		if(v[aa][ii]!=bb)

			isi.pb(dfs(v[aa][ii],aa));

	}

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

	ll sz=isi.size(),jum=0,sisa;

	for(ii=0;ii<sz;ii++)

		jum+=isi[ii];

	sisa=jum-a[aa];

	//cout<<aa<<" "<<jum<<" "<<a[aa]<<" "<<D[aa]<<"_\n";

	//cout<<sisa<<"\n";

	if(sisa<0)

	{

		cout<<"NO\n";

		exit(0);

	}

	ll Z=a[aa]-sisa;

	jum-=Z;

	if((jum%2)==1)

	{

		cout<<"NO\n";

		exit(0);

	}	

	//cout<<isi[sz-1]<<" "<<

	//cout<<jum<<"\n";

	if((isi[sz-1]-Z)>(jum/2))

	{

		cout<<"NO\n";

		exit(0);

	}

	if(Z<0)

	{

		cout<<"NO\n";

		exit(0);

	}

	//cout<<aa<<" "<<Z<<"\n";

	return Z;

}

int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n;

	for(i=1;i<=n;i++)

		cin>>a[i];

	if(n==2)

	{

		if(a[1]==a[2])

			cout<<"YES\n";

		else 

			cout<<"NO\n";

		return 0;

	}

	for(i=1;i<n;i++)

	{

		cin>>ta>>tb;

		v[ta].pb(tb);

		v[tb].pb(ta);

		D[ta]++;

		D[tb]++;

	}

	R=1;

	for(i=1;i<=n;i++)

		if(D[i]>1)

		{

			R=i;

			break;

		}

	//cout<<R<<"\n";

	//for(i=1;i<=n;i++)

	//	cout<<i<<"_"<<D[i]<<"\n";

	if(dfs(R,R)==0)cout<<"YES\n";

	else cout<<"NO\n";

}

// Faster C++ solution for the same problem (measured speedup: 18.868456683913486x):
#include <cstdio>

#include <algorithm>

#define int long long

using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5;

int n;

int head[MAXN] , to[MAXN << 1] , nxt[MAXN << 1] , cnt , ans , du[MAXN << 1];

LL f[MAXN] , a[MAXN];

void add(int u , int v) {nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;}

void dfs(int x , int fa) {

	LL _sum = 0 , mx = 0;

	for (int i = head[x]; i; i = nxt[i]) {

		if(to[i] == fa) continue;

		dfs(to[i] , x);

		if(ans) return;

		mx = max(mx , f[to[i]]);

		_sum += f[to[i]];

	}

	if(!_sum) {

		f[x] = a[x];

		return;

	}

	f[x] = 2ll * a[x] - _sum;

	if(f[x] < 0 || f[x] > a[x] || mx - f[x] > _sum - mx || a[x] < mx) {

		printf("NO");

		exit(0);

	}

}

signed main() {

	scanf("%lld" , &n);

	for (int i = 1; i <= n; ++i) scanf("%lld" , &a[i]);

	if (n == 2) return puts(a[1] == a[2] ? "YES" : "NO"), 0;

	int root = 0;

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

		int u , v;

		scanf("%lld %lld" , &u , &v);

		du[u] ++;du[v] ++;

		add(u , v);add(v , u);

		if(du[u] > 1) root = u;

		if(du[v] > 1) root = v;

	}

	dfs(root , 0);

	if(f[root]) printf("NO");

	else printf("YES");

	return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;

typedef long long ll;

const int N=1e5+5;

int n,k;

ll t[N];

int check(ll p)

{

    int i=0;

    for(int j=0;j<k;j++)

    {

        ll s=0;

        while(s+t[i]<=p)

        {

            s+=t[i];

            i++;

            if(i==n)

                return n;

        }

    }

    return i;

}

ll solve()

{

    ll left=0;

    ll right=100000*10000;

    ll mid;

    while(right-left>1)

    {

        mid=(right+left)/2;

        int v=check(mid);

        if(v>=n) right =mid;

        else left=mid;

    }

    return right;

}

int main()

{

    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>t[i];

    ll ans=solve();

    cout<<ans<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.233237118390559x):
//

// Created by Nivras on 2017/5/16.

//



#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;



const int MAXN = 110000;



long long weight[MAXN];



bool check(const long long load, const long long carNum, const long long goodNum) {

    int cnt = 0;

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

        int nowWeight = 0;

        while (nowWeight + weight[cnt] <= load) {

            nowWeight += weight[cnt];

            cnt++;

            if (cnt == goodNum) {

                return true;

            }

        }

    }

    return false;

}



int main()

{

    long long int n, k;

    scanf("%lld%lld", &n, &k);

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

        scanf("%lld", &weight[i]);

    }



    long long left = 0;

    long long right = 10000 * 100000;

    long long mid;

    while (right - left > 1) {

        mid = (left + right) / 2;

        if (check(mid, k, n)) {

            right = mid;

        }

        else {

            left = mid;

        }

    }

    printf("%lld\n", right);



    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

using namespace std;



typedef long long ll;



const int MAX = 100001;

ll n, k;

ll w[MAX];



ll check(ll p) {

    ll i = 0;

    for (int j = 0; j < k; j++) {

        ll s = 0;

        while (s + w[i] <= p) {

            s += w[i];

            i++;

            if (i == n) return n;

        }

    }

    return i;

}



ll binSearch(ll lo, ll hi) {

    while (hi - lo > 1) {

        ll mi = (lo + hi) >> 1;

        ll v = check(mi);

        if (v >= n) hi = mi;

        else lo = mi;

    }

    return hi;

}



int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    scanf("%lld %lld", &n, &k);

    for (int i = 0; i < n; i++) scanf("%lld", &w[i]);

    ll p = binSearch(0, 100000LL * 10000LL);

    printf("%lld\n", p);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.157849639232919x):
//

// Created by Nivras on 2017/5/16.

//



#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;



const int MAXN = 110000;



long long weight[MAXN];



bool check(const long long load, const long long carNum, const long long goodNum) {

    int cnt = 0;

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

        int nowWeight = 0;

        while (nowWeight + weight[cnt] <= load) {

            nowWeight += weight[cnt];

            cnt++;

            if (cnt == goodNum) {

                return true;

            }

        }

    }

    return false;

}



int main()

{

    long long int n, k;

    scanf("%lld%lld", &n, &k);

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

        scanf("%lld", &weight[i]);

    }



    long long left = 0;

    long long right = 10000 * 100000;

    long long mid;

    while (right - left > 1) {

        mid = (left + right) / 2;

        if (check(mid, k, n)) {

            right = mid;

        }

        else {

            left = mid;

        }

    }

    printf("%lld\n", right);



    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<iostream>

using namespace std;



int n, k;

int a[100050];

long long ans;





bool find(long long p)

{

	long long cnt = 1, l = p;

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

	{

		if (a[i] <= l)

			l -= a[i];

		else

			if (a[i] > p) return 0;

			else

				l = p - a[i], cnt++;

		if (cnt > k) return 0;

	}

	return 1;

}



int main()

{

	scanf("%d%d", &n, &k);

	long long tot = 0;

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

		cin >> a[i], tot += a[i];

	long long l = 0, r = tot;

	while (l<=r)

	{

		long long mid = (l + r) / 2;

		if (find(mid))

			ans = mid, r = mid - 1;

		else

			l = mid + 1;

	}

	cout << ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.248642298415718x):
//

// Created by Nivras on 2017/5/16.

//



#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;



const int MAXN = 110000;



long long weight[MAXN];



bool check(const long long load, const long long carNum, const long long goodNum) {

    int cnt = 0;

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

        int nowWeight = 0;

        while (nowWeight + weight[cnt] <= load) {

            nowWeight += weight[cnt];

            cnt++;

            if (cnt == goodNum) {

                return true;

            }

        }

    }

    return false;

}



int main()

{

    long long int n, k;

    scanf("%lld%lld", &n, &k);

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

        scanf("%lld", &weight[i]);

    }



    long long left = 0;

    long long right = 10000 * 100000;

    long long mid;

    while (right - left > 1) {

        mid = (left + right) / 2;

        if (check(mid, k, n)) {

            right = mid;

        }

        else {

            left = mid;

        }

    }

    printf("%lld\n", right);



    return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;

typedef long long ll;

const int N=1e5+5;

int n,k;

ll t[N];

int check(ll p)

{

    int i=0;

    for(int j=0;j<k;j++)

    {

        ll s=0;

        while(s+t[i]<=p)

        {

            s+=t[i];

            i++;

            if(i==n)

                return n;

        }

    }

    return i;

}

ll solve()

{

    ll left=0;

    ll right=100000*10000;

    ll mid;

    while(right-left>1)

    {

        mid=(right+left)/2;

        int v=check(mid);

        if(v>=n) right =mid;

        else left=mid;

    }

    return right;

}

int main()

{

    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>t[i];

    ll ans=solve();

    cout<<ans<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.240106780914891x):
#include<stdio.h>

const int t=100005;

int a[t];

int n,m;

bool Find(int x)

{

    int sum=0;

    int fuck=0;

    for(int i=1;i<=n;i++)

    {

        sum+=a[i];

        if(sum>x)

        {

            ++fuck;

            sum=a[i];

            if(sum>x)

            {

                return 0;

            }

        }

    }

    return fuck<m;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    int l=1,r=t*10000;

    while(l<=r)

    {

        int mid=l+r>>1;

        if(Find(mid))

        {

            r=mid-1;

        }

        else

            l=mid+1;

    }

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

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

using namespace std;



typedef long long ll;



const int MAX = 100001;

ll n, k;

ll w[MAX];



ll check(ll p) {

    ll i = 0;

    for (int j = 0; j < k; j++) {

        ll s = 0;

        while (s + w[i] <= p) {

            s += w[i];

            i++;

            if (i == n) return n;

        }

    }

    return i;

}



ll binSearch(ll lo, ll hi) {

    while (hi - lo > 1) {

        ll mi = (lo + hi) >> 1;

        ll v = check(mi);

        if (v >= n) hi = mi;

        else lo = mi;

    }

    return hi;

}



int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    scanf("%lld %lld", &n, &k);

    for (int i = 0; i < n; i++) scanf("%lld", &w[i]);

    ll p = binSearch(0, 100000LL * 10000LL);

    printf("%lld\n", p);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.164620340726315x):
#include<stdio.h>

const int t=100005;

int a[t];

int n,m;

bool Find(int x)

{

    int sum=0;

    int fuck=0;

    for(int i=1;i<=n;i++)

    {

        sum+=a[i];

        if(sum>x)

        {

            ++fuck;

            sum=a[i];

            if(sum>x)

            {

                return 0;

            }

        }

    }

    return fuck<m;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    int l=1,r=t*10000;

    while(l<=r)

    {

        int mid=l+r>>1;

        if(Find(mid))

        {

            r=mid-1;

        }

        else

            l=mid+1;

    }

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

}
// Slower C++ solution:
#include<cstdio>

#include<iostream>

using namespace std;



int n, k;

int a[100050];

long long ans;





bool find(long long p)

{

	long long cnt = 1, l = p;

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

	{

		if (a[i] <= l)

			l -= a[i];

		else

			if (a[i] > p) return 0;

			else

				l = p - a[i], cnt++;

		if (cnt > k) return 0;

	}

	return 1;

}



int main()

{

	scanf("%d%d", &n, &k);

	long long tot = 0;

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

		cin >> a[i], tot += a[i];

	long long l = 0, r = tot;

	while (l<=r)

	{

		long long mid = (l + r) / 2;

		if (find(mid))

			ans = mid, r = mid - 1;

		else

			l = mid + 1;

	}

	cout << ans << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.255532183296788x):
#include<stdio.h>

const int t=100005;

int a[t];

int n,m;

bool Find(int x)

{

    int sum=0;

    int fuck=0;

    for(int i=1;i<=n;i++)

    {

        sum+=a[i];

        if(sum>x)

        {

            ++fuck;

            sum=a[i];

            if(sum>x)

            {

                return 0;

            }

        }

    }

    return fuck<m;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    int l=1,r=t*10000;

    while(l<=r)

    {

        int mid=l+r>>1;

        if(Find(mid))

        {

            r=mid-1;

        }

        else

            l=mid+1;

    }

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

}