CF883C.Downloading B++

Only T milliseconds left before the start of well-known online programming contest Codehorses Round 2017.

Polycarp needs to download B++ compiler to take part in the contest. The size of the file is f bytes.

Polycarp's internet tariff allows to download data at the rate of one byte per _t_0 milliseconds. This tariff is already prepaid, and its use does not incur any expense for Polycarp. In addition, the Internet service provider offers two additional packages:

• download _a_1 bytes at the rate of one byte per _t_1 milliseconds, paying _p_1 burles for the package;
• download _a_2 bytes at the rate of one byte per _t_2 milliseconds, paying _p_2 burles for the package.

Polycarp can buy any package many times. When buying a package, its price (_p_1 or _p_2) is prepaid before usage. Once a package is bought it replaces the regular tariff until package data limit is completely used. After a package is consumed Polycarp can immediately buy a new package or switch to the regular tariff without loosing any time. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.

Find the minimum amount of money Polycarp has to spend to download an f bytes file no more than in T milliseconds.

Note that because of technical reasons Polycarp can download only integer number of bytes using regular tariff and both packages. I.e. in each of three downloading modes the number of downloaded bytes will be integer. It means that Polycarp can't download a byte partially using the regular tariff or/and both packages.

距离著名的在线编程竞赛 Codehorses Round 2017 开始仅剩 T 毫秒。

Polycarp 需要下载 B++ 编译器以参加本次竞赛。该文件大小为 f 字节。

Polycarp 的互联网套餐允许以每字节 _t_₀ 毫秒的速率下载数据。该套餐已预付费，且 Polycarp 使用它不会产生任何额外费用。此外，互联网服务提供商还提供两种附加套餐：

• 以每字节 _t_₁ 毫秒的速率下载 _a_₁ 字节，需支付 _p_₁ burles（币种）购买该套餐；
• 以每字节 _t_₂ 毫秒的速率下载 _a_₂ 字节，需支付 _p_₂ burles 购买该套餐。

Polycarp 可以多次购买任一套餐。购买套餐时，其价格（_p_₁ 或 _p_₂）需预先支付。一旦购买某套餐，它将立即取代常规套餐，直至该套餐所含的数据额度被完全用尽。当某套餐被完全消耗后，Polycarp 可立即购买新的套餐，或无缝切换回常规套餐（不损失任何时间）。在某套餐生效期间，Polycarp 不得再购买其他套餐，也不得切换回常规互联网套餐。

请计算 Polycarp 为在至多 T 毫秒内完成下载一个 f 字节的文件所需花费的最少金额（单位：burles）。

注意：由于技术原因，Polycarp 在常规套餐及两种附加套餐下，每次下载的字节数均为整数。即，在这三种下载模式中，下载的字节数均为整数。这意味着 Polycarp 无法使用常规套餐和/或任一附加套餐对单个字节进行部分下载。

The first line contains three integer numbers f, T and _t_0 (1 ≤ f, T, _t_0 ≤ 107) — size of the file to download (in bytes), maximal time to download the file (in milliseconds) and number of milliseconds to download one byte using the regular internet tariff.

The second line contains a description of the first additional package. The line contains three integer numbers _a_1, _t_1 and _p_1 (1 ≤ _a_1, _t_1, _p_1 ≤ 107), where _a_1 is maximal sizes of downloaded data (in bytes), _t_1 is time to download one byte (in milliseconds), _p_1 is price of the package (in burles).

The third line contains a description of the second additional package. The line contains three integer numbers _a_2, _t_2 and _p_2 (1 ≤ _a_2, _t_2, _p_2 ≤ 107), where _a_2 is maximal sizes of downloaded data (in bytes), _t_2 is time to download one byte (in milliseconds), _p_2 is price of the package (in burles).

Polycarp can buy any package many times. Once package is bought it replaces the regular tariff until package data limit is completely used. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.

第一行包含三个整数 $f$、$T$ 和 $t_0$（$1 \le f,\,T,\,t_0 \le 10^7$）——分别表示待下载文件的大小（单位：字节）、下载该文件的最大允许时间（单位：毫秒）以及使用普通互联网资费每下载 1 字节所需的时间（单位：毫秒）。

第二行描述第一个附加套餐。该行包含三个整数 $a_1$、$t_1$ 和 $p_1$（$1 \le a_1,\,t_1,\,p_1 \le 10^7$），其中 $a_1$ 表示该套餐允许下载的数据量上限（单位：字节），$t_1$ 表示使用该套餐时每下载 1 字节所需的时间（单位：毫秒），$p_1$ 表示该套餐的价格（单位：burles）。

第三行描述第二个附加套餐。该行包含三个整数 $a_2$、$t_2$ 和 $p_2$（$1 \le a_2,\,t_2,\,p_2 \le 10^7$），其中 $a_2$ 表示该套餐允许下载的数据量上限（单位：字节），$t_2$ 表示使用该套餐时每下载 1 字节所需的时间（单位：毫秒），$p_2$ 表示该套餐的价格（单位：burles）。

Polycarp 可以多次购买任意一个套餐。一旦购买某个套餐，它将立即取代普通互联网资费，直至该套餐所含的数据配额被完全用尽。在某个套餐生效期间，Polycarp 既不能购买其他套餐，也不能切换回普通互联网资费。

Print the minimum amount of money that Polycarp needs to pay to download B++ compiler no more than in T milliseconds. If there is no solution, print the only integer -1.

输出 Polycarp 在不超过 T 毫秒的时间内下载 B++ 编译器所需的最少金额。若无解，则仅输出整数 -1。

In the first example Polycarp has to buy the first additional package 5 times and do not buy the second additional package. He downloads 120 bytes (of total 26·5 = 130 bytes) in 120·8 = 960 milliseconds (960 ≤ 964). He spends 8·5 = 40 burles on it.

In the second example Polycarp has enough time to download 10 bytes. It takes 10·20 = 200 milliseconds which equals to upper constraint on download time.

In the third example Polycarp has to buy one first additional package and one second additional package.

In the fourth example Polycarp has no way to download the file on time.

在第一个例子中，Polycarp 必须购买第一种附加套餐 5 次，且不购买第二种附加套餐。他下载了 120 字节（总共可下载 $26 \times 5 = 130$ 字节），耗时 $120 \times 8 = 960$ 毫秒（满足 $960 \leq 964$）。他为此花费了 $8 \times 5 = 40$ burles。

在第二个例子中，Polycarp 有足够的时间下载 10 字节。所需时间为 $10 \times 20 = 200$ 毫秒，恰好等于下载时间的上限约束。

在第三个例子中，Polycarp 必须购买一份第一种附加套餐和一份第二种附加套餐。

在第四个例子中，Polycarp 无法在规定时间内下载完该文件。