题解

题面描述

本题要求采购汽车以满足载人和载货的需求：至少载 $X$ 人和至少承载 $Y$ 立方米货物。市场上共有 $n$ 种汽车，每种汽车有一种默认方案和若干种选配方案。

• 对于第 $i$ 种汽车，默认方案的花费为 $m_i$ 元，载人能力为 $x_i$ 人，载货能力为 $y_i$ 立方米；
• 同时，第 $i$ 种汽车有 $k_i$ 种选配方案，每个选配方案会使得花费增加 $m_{ij}$ 元，载人能力变化 $x_{ij}$，载货能力变化 $y_{ij}$。

每辆车只能采用一种方案（默认或某个选配方案），且可以无限制地采购任意种汽车的任一方案。目标是在满足至少 $X$ 人和 $Y$ 立方米的条件下，花费最少金额。

题目内容

小李负责公司的汽车采购业务。最近公司需要采购一批汽车，保证其可以载$X$人，承货$V$立方米。

小李调研了市场的$n$种汽车。对第$i$种汽车价值$m_i$元，有$k_i$种选配方案。默认的方案可以承载$x_i$人，承货$y_i$立方米。第$j$种选配方案需要金额变化为$m_{ij}$元，可以选配特殊的座椅或者支架使得载人和承货能力发生变化，载人变化值为$x_{ij}$，载货变化值为$y_{ij}$。每辆车只能选择一种选配方案，或者选择默认方案。

小李可以同时采购多种汽车的多种选配方案，只希望花费最少的金额满足要求。

输入描述

第一行包括三个正整数$X,Y,n$，这三个数取值范围都在[$1,200$]中。

然后是$n$组数据:

其中第$i$组第一行包括四个整数$m_i,x_i,y_i,k_i$，所有数均小于$1e5,k_i$可能为$0$。

接下来$k_i$行每行包括$3$个整数$m_{ij},x_{ij},y_{ij}$，所有数的绝对值均小于$1e5$。

数据保证$k_i$之和小于$200-n$，选配后的总价格，载人、承货均为正整数

输出描述

输出一个整数，表示最少花费金额。

样例1

输入

10 20 2
100 2 6 1
20 1 1
80 5 1 1
10 -1 2

输出

390