# [Editorial] Buns

## Đề bài
Lavrenty, a baker, is going to make several buns with stuffings and sell them.

Lavrenty has $n$ grams of dough as well as $m$ different stuffing types. The stuffing types are numerated from $1$ to $m$. Lavrenty knows that he has $a_i$ grams left of the $i$-th stuffing. It takes exactly $b_i$ grams of stuffing $i$ and $c_i$ grams of dough to cook a bun with the $i$-th stuffing. Such bun can be sold for $d_i$ tugriks.

Also he can make buns without stuffings. Each of such buns requires $c_0$ grams of dough and it can be sold for $d_0$ tugriks. So Lavrenty can cook any number of buns with different stuffings or without it unless he runs out of dough and the stuffings. Lavrenty throws away all excess material left after baking.

Find the maximum number of tugriks Lavrenty can earn.

[Link bài trên Codeforces](https://codeforces.com/problemset/problem/106/C)

## Tóm tắt

Tìm số tiền nhiều nhất bán bánh kiếm được từ $n$ gram bột.

Có thể làm 2 loại bánh:

+ Bánh có nhân: loại thứ $i$ có $a_i$ gram nhân; cần $b_i$ gram nhân và $c_i$ bột để làm 1 cái; bán 1 cái được $d_i$.
+ Bánh không nhân: cần $c_0$ bột để làm 1 cái; bán đi được $d_0$.

## Rằng buộc

$1 \le n \le 10^3$
$1 \le m \le 10$
$1 \le a_i, b_i, c_i, d_i, c_0, d_0 \le 100$

## Lời giải

Chúng ta sẽ sử dụng quy hoạch động.

$dp[i][j]$ là số tiền nhiều nhất kiếm được sử dụng $i$ bột và bán bánh loại nhân từ $1$ -> $j$ (chưa dùng đến bánh không nhân).

$dp[i][0] = 0$ $\forall i$ (không dùng đến bánh có nhân)

$dp[i][j] = max(dp[i - c[j] * k][j - 1] + d[j] * k)$ $(\forall k, 0 \le k \le a[j]/b[j])$
($k$ là số bánh với nhân $j$)

Đáp án sẽ là $max(dp[i][m] + ((n - i) / c_0) * d_0)$ $(\forall i, 0 \le i \le n)$
($n - i$ là số bột còn lại -> làm được $((n - i) / c_0)$ cái bánh, bán mỗi cái được $d_0$)

## Code

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

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

    int n, m, c0, d0;
    cin >> n >> m >> c0 >> d0;
    
    vector<int> a(m + 1), b(m + 1), c(m + 1), d(m + 1);
    for(int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for(int dough = 0; dough <= n; dough++) {
        for(int bun = 1; bun <= m; bun++) {
            for(int times = 0; times <= (a[bun] / b[bun]); times++) {
                if(dough >= times * c[bun]) {
                    dp[dough][bun] = max(
                        dp[dough][bun], 
                        dp[dough - times * c[bun]][bun - 1] + d[bun] * times);
                }
            }
        }    
    }

    int ans = 0;
    for(int dough = 0; dough <= n; dough++) {
        ans = max(ans, dp[dough][m] + ((n - dough) / c0) * d0);   
    }

    cout << ans << '\n';
}

*Nguyễn Hoàng Dũng 2021-10-15*