stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef pair<int, int> ii;

typedef pair<int, ii> iii;



const int MAX = 2e5+1;



bool ok = true;

vector<vector<int>> g;

vector<ll> a;



ll go(int u, int p) {

    ll sum = 0;

    bool leaf = true;

    vector<ll> d(g[u].size());

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

        int v = g[u][i];

        if(v != p) {

            leaf = false;

            d[i] = go(v, u);

            sum += d[i];

        }

    }

//    cout << u << " - " << sum << endl;

    if(leaf || (p == -1 && g[u].size() == 1)) {

        if(p == -1) ok &= sum == a[u];

        return a[u];

    }

    ll r = 2*a[u] - sum;

//    cout << u << " " << r << " " << sum << endl;

    if(p != -1) ok &= r >= 0;

    if(p != -1) sum += r;

    ok &= sum == 2*a[u];

    ok &= sum % 2 == 0;

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

        ok &= d[i] <= sum/2;

    }

    ok &= r <= sum/2;

    return r;

}



int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    #ifdef LOCAL

        freopen("input.txt", "r", stdin);

        freopen("output.txt", "w", stdout);

    #else

        #define endl '\n'

    #endif



    int n; cin >> n;

    g.assign(n+1, vector<int>());

    a.assign(n+1, 0);



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

        cin >> a[i];

    }



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

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

        g[a].push_back(b);

        g[b].push_back(a);

    }



    go(1, -1);



    if(ok) cout << "YES" << endl;

    else cout << "NO" << endl;



}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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";

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//

// Created by Chisec Coin on 17/7/15.

//



#include <iostream>

#include <string>

#include <cmath>

#include <cstring>

#include <vector>

#include <algorithm>

#include <set>

#include <queue>

#include <sstream>

#include <map>

const int NIL = -1;

typedef long long ll;

using std::cin;using std::cout;using std::endl;using std::max;using std::min;



int n, k;

ll w[100005];



int check(ll p) {

    int i = 0;

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

        ll s = 0;

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

            s += w[i++];

            if (i == n) {

                return n;

            }

        }

    }

    return i;

}



int solve() {

    ll left = 0;

    ll right = 100000 * 10000;

    ll mid;

    while (right - left > 1) {

        mid = (left + right) / 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 >> w[i];

    }

    ll ans = solve();

    cout << ans << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const ll maxn = 1e5 + 10;

ll a[maxn];

ll n, k;

ll check(ll p) {

	ll i = 0;

	ll temp = 0, nk = k-1;

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

		if (temp + a[i] <= p) {

			temp += a[i];

		}

		else if(nk>0&&a[i]<=p){

			temp = a[i];

			nk--;

		}

		else {

			return i;

		}

	}

	return i+1;

}

int main() {

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

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

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

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

	}

	ll l = 0, r = 1e9;

	while (l < r -1) {

		ll m =(r+l)/2;

		if (check(m) >= n) {

			r = m;

		}

		else {

			l = m;

		}

	}

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

	return 0;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const int maxn = 1e5 + 10;

int a[maxn];

int n, k;

int check(int p) {

	int i = 0;

	int temp = 0, nk = k-1;

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

		if (temp + a[i] <= p) {

			temp += a[i];

		}

		else if(nk>0&&a[i]<=p){

			temp = a[i];

			nk--;

		}

		else {

			return i;

		}

	}

	return i+1;

}

int main() {

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

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

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

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

	}

	int l = 0, r = 1e9;

	while (l < r -1) {

		int m =(r+l)/2;

		if (check(m) >= n) {

			r = m;

		}

		else {

			l = m;

		}

	}

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

	return 0;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

#define MAX 100000

typedef long long llong;

int n,k;

llong T[MAX];

int check(llong P)

{

    int i=0;

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

    {

        llong s=0;

        while(s+T[i]<=P)

        {

            s+=T[i];

            i++;

            if(i==n)return n;

        }

    }

    return i;

}

int solve()

{

    llong left=0;

    llong right=100000*10000;

    llong mid;

    while(right-left>1)

    {

        mid=(left+right)/2;

        int v=check(mid);

        if(v>=n)right=mid;

        else left=mid;

    }

    return right;

}

main()

{

    cin>>n>>k;

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

    llong ans=solve();

    cout<<ans<<endl;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<iostream>

using namespace std;

#define Max 100000

int n,k;

typedef long long llong;

llong  T[Max];

int check (llong  P)

{

    int i=0;

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

    {

        llong sum=0;

        while(sum+T[i]<=P)

        {

             sum+=T[i];

            i++;

            if(i==n)

                return n;

        }

    }

    return i;

}

int solve()

{

    llong left=0;

    llong right=100000*10000;

    llong mid;

    while(right-left>1)

    {

        mid=(left+right)/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];

    }

   llong ans=solve();

   cout<<ans<<endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem: