Description

$XXX$上山去采药。$XXX$有一个最大承重为$m(1<=m<=100)$且容积为$t(1<= t<=100)$的背包，他所采集的药材的总重量不能大于背包的最大承重且总体积不能大于背包的容积。已知共有$n(1<=n<=1000)$株药材，并且知道每株药材的重量$w1(1<=w1<=m)$、体积$w2(1<=w2<=t)$及价值$v(1<=v<=100000)$，如何选择，才能使得采到的药材的总价值最大？

Format

Input

第$1$行为三个整数$m$、$t$和$n$，分别为背包的最大承重、容积及药材的数量。 第$2$至$n+1$行每行三个整数$w1$、$w2$和$v$，分别表示每株药材的重量、体积及价值。

Output

能采到的药材的最大总价值

Samples

100 100 5
50 60 100
60 50 120
50 50 115
40 60 21
40 50 5

125