← 返回题目列表

Codeforces · 883/C

C. 下载 B++

中文机器翻译题面 查看原题

距离知名在线编程大赛 Codehorses Round 2017 开始仅剩 T 毫秒。

Polycarp需要下载B++编译器才能参加比赛。文件的大小为 f 字节。

Polycarp 的互联网资费允许以每 t0 毫秒一个字节的速率下载数据。该关税已经预付,其使用不会给波利卡普带来任何费用。此外,互联网服务提供商还提供两个额外的套餐:

- 以每 t1 毫秒一个字节的速率下载 a1 字节,为包支付 p1 burles;
- 以每 t2 毫秒一个字节的速率下载 a2 字节,为包支付 p2 burles。

波利卡普可以多次购买任意礼包。购买套餐时,其价格(p1 或 p2)在使用前预付。购买套餐后,它将取代常规资费,直到套餐数据限制完全用完为止。消耗完一个套餐后,Polycarp 可以立即购买新套餐或切换到常规资费,不会浪费任何时间。当套餐正在使用时,Polycarp 无法购买另一个套餐或切换回常规互联网资费。

求 Polycarp 下载一个不超过 T 毫秒的 f 字节文件所需花费的最低金额。

请注意,由于技术原因,Polycarp 只能使用常规资费和两个软件包下载整数字节。 IE。在三种下载模式中,每一种下载的字节数都是整数。这意味着 Polycarp 无法使用常规资费或/和两个软件包部分下载字节。

输入

第一行包含三个整数 f、T 和 t0 (1 ≤ f, T, t0 ≤ 107) — 要下载的文件大小(以字节为单位)、下载文件的最长时间(以毫秒为单位)以及使用常规互联网资费下载一个字节的毫秒数。

第二行包含第一个附加包的描述。该行包含三个整数a1、t1和p1(1≤a1、t1、p1≤107),其中a1是下载数据的最大大小(以字节为单位),t1是下载一个字节的时间(以毫秒为单位),p1是包的价格(以burles为单位)。

第三行包含第二个附加包的描述。该行包含三个整数a2、t2和p2(1≤a2、t2、p2≤107),其中a2是下载数据的最大大小(以字节为单位),t2是下载一个字节的时间(以毫秒为单位),p2是包的价格(以burles为单位)。

波利卡普可以多次购买任意礼包。购买套餐后,它将取代常规资费,直到套餐数据限制完全用完为止。当套餐正在使用时,Polycarp 无法购买另一个套餐或切换回常规互联网资费。

输出

打印 Polycarp 下载 B++ 编译器所需支付的最低金额,不超过 T 毫秒。如果无解,则打印唯一的整数-1。

示例

输入 #1

120 964 20
26 8 8
13 10 4

输出 #1

40

输入 #2

10 200 20
1 1 1
2 2 3

输出 #2

0

输入 #3

8 81 11
4 10 16
3 10 12

输出 #3

28

输入#4

8 79 11
4 10 16
3 10 12

输出#4

-1

注意

在第一个示例中,Polycarp 必须购买第一个附加包 5 次,并且不要购买第二个附加包。他在 120·8 = 960 毫秒 (960 ≤ 964) 内下载了 120 个字节(总共 26·5 = 130 个字节)。他为此花费了 8·5 = 40 节。

在第二个示例中,Polycarp 有足够的时间下载 10 个字节。需要 10·20 = 200 毫秒,相当于下载时间的上限。

在第三个示例中,Polycarp 必须购买一个第一附加包和一个第二附加包。

在第四个示例中,Polycarp 无法按时下载文件。