2016 T1 买铅笔

主知识点：枚举。交叉标签：枚举、数学。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 pencil.in / pencil.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：官网数据；与公开存档逐文件一致。

题目描述

需要购买至少 $n$ 支铅笔。商店提供三种包装，每种包装有给定的支数和价格，且库存不限。只能选择一种包装购买，包装不可拆开。求满足数量要求的最小总花费。

输入格式

第一行包含一个正整数 $n$，表示需要的铅笔数量。

接下来三行，每行用 $2$ 个正整数描述一种包装的铅笔：其中第 $1$ 个整数表示这种包装内铅笔的数量，第 $2$ 个整数表示这种包装的价格。

保证所有的 $7$ 个数都是不超过 $10000$ 的正整数。

输出格式

$1$ 个整数，表示 P 老师最少需要花费的钱。

样例

样例 1

输入：

57
2 2
50 30
30 27

输出：

54

样例 2

输入：

9998
128 233
128 2333
128 666

输出：

18407

样例 3

输入：

9999
101 1111
1 9999
1111 9999

输出：

89991

数据范围与特殊性质

所有输入数都为 $[1,10000]$ 内的整数。

测试点	$n$ 是否为各包装支数的整倍数	包装支数特点
1~4	是	三种支数相同
5~8	否
9~12	是	后两种支数相同
13~16	否
17~18	是	无其他限制
19~20	否

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P1909
• 赛事：NOIP 普及组复赛（CSP-J 前身） 2016。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。