比赛场次 400
比赛名称 NOIP2017普及组模拟赛Mike
比赛状态 已结束比赛成绩
开始时间 2017-09-30 12:00:00
结束时间 2017-09-30 14:00:00
开放分组 全部用户
注释介绍 真的是普及组大水题……
题目名称 潜水员的问题
输入输出 ple.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarPine AAAAAAAAAA 0.000 s 0.03 MiB 100
Gravatar路人甲 AAAAAAAAAA 0.033 s 0.31 MiB 100
Gravatarユッキー AAAAAAAAAA 0.040 s 0.38 MiB 100
Gravatar李兴臣 AAAAAAAAAA 0.070 s 0.18 MiB 100

潜水员的问题

★★   输入文件:ple.in   输出文件:ple.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

一个潜水员在潜水时使用一种特殊的装置:一个有两个容器的气筒。一个容器中装的是氧气,另一个容器中装氮气。潜水员需要携带的氧气和氮气量依赖于潜水的时间和深度。潜水员有一系列的气筒,用来在不同的情况下携带。每个气筒可以用这样几个量来描述:气筒的质量,气筒中所能容纳的氧气量,以及可以容纳的氮气量。为了能完成最近的一个任务,潜水员需要一定量的氧气和氮气。潜水员有一系列准备好的气筒。他希望能携带总质量尽可能小的气筒下水。现在请你帮他计算一下至少要携带多少质量的气筒下水才能完成这个任务。

注意:题目中给出的气筒总是能够容纳足够多的气体使得潜水员能完成任务。

【输入格式】

第一行有两个整数 t 和 a ,分别描述完成任务所需的氧气和氮气量。( 1 ≤ t ≤ 21 , 1 ≤ a ≤ 79 )。

第二行有一个整数 n ,表示气筒的个数。( 1 ≤ n ≤ 1000 )。

以后 n 行中,每行有三个整数 ti , ai , wi , ti 表示第 i 个气筒所能容纳的氧气量, ai 表示第 i 个气筒所能容纳的氮气量, wi 表示气筒 i 的质量。( 1 ≤ ti ≤ 21 , 1 ≤ ai ≤ 79 , 1 ≤ wi ≤ 800 )。

【输出格式】

输出只有一行,包含一个整数,表示最少需要携带的多少质量的气筒来完成该任务。

【输入样例】

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

【输出样例】

249

【样例解释】

潜水员有以下 5 个气筒,每个气筒用三个整数来描述:气筒所能容纳的氧气的量,氮气的量和气筒的质量:

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

这次任务中潜水员需要携带5升氧气, 60升氮气,那么他至少要携带总质量为 249 的气筒下水(样例中的第一个和第二个气筒或者第四个和第五个气筒)。