Downloading B++

## 题目描述 距离知名的线上编程大赛Codehorses Round 2017只剩 _T_ 毫秒啦！ Polycarp需要下载B++的编译器来参加这次比赛。文件的大小是 _f_ 字节。 Polycarp的网络套餐能让他以每 _t0_ 秒1字节的速度下载。这个套餐已经付过费了，它的使用也不会导致任何费用。除此以外，互联网服务的提供商额外提供了两个下载包： - 以每 _t1_ 毫秒1字节的速度下载 _a1_ 字节，价格是 _p1_ “burles”~~（这个单词没查到，反正就是钱的单位）~~。 - 以每 _t2_ 毫秒1字节的速度下载 _a2_ 字节，价格是 _p2_ “burles”。 这些包可以任意购买。买包时，它的价格（ _p1_ 或 _p2_ ）是提前付款的。一旦一个包被购买，它就会取代常规的网络套餐直到到达下载上限。在一个包用完后，Polycarp可以立即买新包或者调到常规的套餐（不损失时间）。一个包正在使用时，Polycarp不能再买包或者调回常规套餐。 你的任务就是找到Polycarp最少需要花多少钱才能在 _T_ 毫秒内下载一个 _f_ 字节的文件。 注意：因为技术原因，不管用哪种手段（常规套餐或下载包），Polycarp的下载的字节数**都是整数**, 即三种下载方式的下载字节数都会是整数。也就是说，Polycarp不能用常规套餐和/或下载包来分块地下载一个字节。 ## 输入输出格式 ### 输入格式: 第一行有三个整数 _f_,_T_ 和 _t0_ (1 <= _f_,_T_,_t0_ <= 1e7)，具体含义见题目描述。 第二行有第一个下载包的描述，即 _a1_, _t1_ 和_p1_ (1 <= _a1_, _t1_ ,_p1_ <= 1e7)，具体含义见题目描述。 第三行有第二个下载包的描述，即 _a2_, _t2_ 和_p2_ (1 <= _a2_, _t2_ ,_p2_ <= 1e7)，具体含义见题目描述。 ### 输出格式: 输出Polycarp最少需要多少钱（也就是多少"burles"啦）才能在T毫秒内下载好B++编译器。无解输出-1。 ## 说明 在样例一中，Polycarp需要买第一个下载包5次、买第二个下载包0次。他在120×8 = 960毫秒（960 <= 964）内下载了120字节（其实一共下载了26×5 = 130字节）。他总共花了8×5 = 40 "burles"。 在样例二中，Polycarp有足够的时间去下载10字节。花费的时间（10×20 = 200毫秒）等于上限。 在样例三中，Polycarp需要买第一个下载包1次，第二个下载包1次。 在样例四中，Polycarp无法按时下载。

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.

The first line contains three integer numbers $ f $ , $ T $ and $ t_{0} $ ( $ 1<=f,T,t_{0}<=10^{7} $ ) — 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}<=10^{7} $ ), 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}<=10^{7} $ ), 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.

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.

120 964 20
26 8 8
13 10 4

40

10 200 20
1 1 1
2 2 3

0

8 81 11
4 10 16
3 10 12

28

8 79 11
4 10 16
3 10 12

-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.