距离知名在线编程大赛 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 无法按时下载文件。