TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1123
  • Problem
  • P1123潜水员
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸:一个为氧气,一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少?
    例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119
    如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。
    你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

    Input Format

    第一行有2整数t,a(1<=t<=21,1<=a<=79)。它们表示氧,氮各自需要的量。
    第二行为整数n(1<=n<=1000)表示气缸的个数。
    此后的n行,每行包括ti,ai,wi(1<=ti<=21,1<=ai<=79,1<=wi<=800)3整数。这些各自是:第i个气缸里的氧和氮的容量及汽缸重量。

    Output Format

    仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。

    Sample Input

    5 60
    5
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119

    Sample Output

    249