在一个遥远的泰伦殖民地上，人们发现了一件可能扭转战争局势的文物。与此同时，情报部门报告称，一支虫群正在向该殖民地移动。必须在援军到达之前不惜一切代价保护这件文物。

你拥有 $m$ 单位的矿物和 $g$ 单位的瓦斯。此外，还有 $n$ 种可供建造的防御建筑。建造一个第 $i$ 种类型的建筑需要 $a_i$ 单位的矿物和 $b_i$ 单位的瓦斯，并能增加 $c_i$ 单位的基地防御力。你可以建造任意数量（包括零个）的任何类型的建筑，前提是所有建筑消耗的矿物和瓦斯总量分别不超过 $m$ 和 $g$。

请确定在给定约束条件下，所能达到的最大总防御力。

输入格式

第一行包含三个整数 $m$、$g$ 和 $n$ —— 分别表示可用的矿物单位数、瓦斯单位数以及建筑类型数量（$0 \le m \le 1000$，$0 \le g \le 1000$，$1 \le n \le 10$）。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $c_i$ —— 分别表示建造一个第 $i$ 种类型的建筑所需的矿物单位数、瓦斯单位数及其提供的防御力（$1 \le a_i \le 100$，$0 \le b_i \le 100$，$0 \le c_i \le 100$）。

输出格式

输出一个整数 —— 所能达到的最大总防御力。

样例

样例输入 1

10 10 3
7 0 6
6 2 7
2 5 5

样例输出 1

12

样例输入 2

11 10 3
7 0 6
6 2 7
2 5 5

样例输出 2

16

说明

在第一个样例中，最优方案是建造一个第 2 种类型的建筑和一个第 3 种类型的建筑。

在第二个样例中，最有利的方案是建造一个第 1 种类型的建筑和两个第 3 种类型的建筑。