前置知识：分组背包

由于每组的物品是互斥的，在进行背包dp时，对于每个给定的背包容量，我们只能在当前组别选一件物品。
滚动数组优化后：设dp[j]为容量为j时取得的最大价值，当前考虑到第i组。

如果这一组有k个物品，第l个物品的空间是w[l],价值为c[l]，那么我们的状态转移方程为

$$dp[j] = max\{dp[j],dp[j-w[1]]+c[1],dp[i-w[2]]+c[2], ... ,dp[j-w[k]]+c[k]\}$$

对比01背包 可以将01背包看成每一组只有一个物品的分组背包，则对于当前物品(w,c)的状态转移方程为

$$dp[j] = max\{dp[j],dp[j-w]+c\}$$

如果每组有两个，则转移方程为

$$dp[j] = max\{dp[j],dp[j-w[1]]+c[1],dp[j-w[2]]+c[2]\}$$

那么如果每组有k个，就能得到上文给出的分组背包的状态转移方程。(不难发现，每组的k不一样也无所谓)

下面我们来分析这道题：

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

/*
    题目分析：
        这显然是一个背包题目。
        由于对于物品i，数量（即开销）x与价值Ai*x^Bi并不成正比，即不满足

                        W(x) = W(x-m)+W(m)

                        （W(x)为选择x件物品时的价值）
        我们无法将x件物品与x-m件物品与m件物品等同（2件物品的价值并不是两个1件物品的价值）
        故将每种数量情况分开考虑

        由于每个论题的论文数量情况只有一种，该背包为分组01背包，每个论题为一组。
*/
#define int long long
int n,m,a[30],b[30],dp[205];

int f(int x,int i){
    int ans = 1;
    for(int k=0;k<b[i];k++)
        ans*=x;
    return a[i]*ans;
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>a[i]>>b[i];
    memset(dp,0x3f,sizeof(dp));
    dp[0] = 0;
    for(int i=0;i<m;i++)
        for(int j=n;j>=0;j--)
            for(int k=0;k<=j;k++)
                dp[j] = min(dp[j],dp[j-k]+f(k,i));
    cout<<dp[n];
    return 0;
}