// 数列分段 对于给定的一个长度为 N 的正整数数列 A  i ​  ，现要将其分成连续的若干段，并且每段和不超过 M（可以等于 M），问最少能将其分成多少段使得满足要求。

#include<iostream>
using namespace std;
int main()
{
    int n,m,a[100000];
    int temp=0,result=1;
    int i;
    
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>a[i];
    
    for(i=1;i<=n;i++)
    {
        if(a[i]+temp>m)
        {
            result++;
            temp=0;
        } 
        temp+=a[i];
    }
    
    cout<<result<<endl;
    return 0;
}

// 纪念品分组 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int w, n;
    std::cin >> w;
    std::cin >> n;

    std::vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> prices[i];
    }

    std::sort(prices.begin(), prices.end());

    int left = 0, right = n - 1;
    int groups = 0;

    while (left <= right) {
        if (prices[left] + prices[right] <= w) {
            ++left;
            --right;
        } else {
            --right;
        }
        ++groups;
    } 
    std::cout << groups << std::endl;

    return 0;
}

// 合并果子，在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

long long sum = 0;  
priority_queue<int, vector<int>, greater<int>> q;  

bool comp(int a, int b) {
    return a < b;
}

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

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        q.push(x);  
    }

    while (q.size() != 1) {
        int a = q.top();  
        q.pop();
        int b = q.top(); 
        q.pop();

        sum += (a + b);  
        q.push(a + b);   
    }

    cout << sum << endl;  
    return 0;
}

// 装箱子，有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。  现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

#include<iostream>
using namespace std;
using ll = long long;
const int N = 2e4 + 9;
ll dp[N], v[N];

void solve()
{
ll V, n; cin >> V >> n;
for (int i = 1; i <= n; ++i) cin >> v[i];
for (int i = 1; i <= n; ++i)
{
for (int j = V; j >= v[i]; --j)
{
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
}
}

cout << V - dp[V];
}

int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}

// 采药， 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药

#include <iostream>

using namespace std;

const int N = 110, M = 1010;

int dp[M], t[N], w[N];
int n, m;

void input() {
    cin >> m >> n;
    for(int i = 1; i <= n; ++ i) cin >> t[i] >> w[i];
}

void solve() {
    for(int  i = 1; i <= n; ++ i) 
        for(int j = m; j >= t[i]; -- j) 
            dp[j] = max(dp[j], dp[j - t[i]] + w[i]);
}

int main(){
    input();

    solve();
    cout << dp[m] << endl;
    return 0;
}