P6646 - 卖东西 - ZUFEOJ

内存限制：256 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：2 通过：2

提交提交记录统计 Web Board

第一行两个整数 $m,n$。

下面 $n$ 行，第 $i+1$ 行三个整数 $a_i,b_i,c_i$ 与一个字符串 $st_i$。

最多卖的钱 $s$。

## 样例 #1

### 样例输入 #1

```

20 3

63 1 64 yinshifen

1 10 1 men

1 1 64 yinshifen

```

### 样例输出 #1

```

64

```

## 提示

数据保证：

- $0\leq m\leq 21$；

- $0\leq n\leq 100$；

- $0\leq a_i\leq 1344$；

- $0\leq b_i\leq 10^4$；

- $0<c_i\leq 64$；

- $0<|st_i|<100$；

- $0\leq s\leq 10^6$。

**注：数据强大，搜索 $0$ 分，请使用多重背包。**

20 3
63 1 64 yinshifen
1 10 1 men
1 1 64 yinshifen

DP