Tải B++

Chỉ còn $T$ mili giây trước khi cuộc thi bắt đầu, Polycarp cần tải về một tệp có kích thước $f$ byte.

Gói cước mặc định (đã trả trước, không tốn thêm tiền) cho phép tải mỗi byte mất $t_0$ mili giây. Ngoài ra nhà mạng còn bán hai gói bổ sung:

• Gói 1: tải tối đa $a_1$ byte, mỗi byte mất $t_1$ mili giây, giá $p_1$.
• Gói 2: tải tối đa $a_2$ byte, mỗi byte mất $t_2$ mili giây, giá $p_2$.

Mỗi gói có thể mua bao nhiêu lần tùy ý, trả tiền ngay khi mua. Khi một gói được mua, nó thay thế gói cước mặc định cho đến khi dùng hết dung lượng của gói; trong thời gian đó không được mua gói khác hay quay lại gói cước mặc định. Khi gói đã dùng hết, Polycarp có thể ngay lập tức mua gói mới hoặc chuyển về gói cước mặc định mà không mất thời gian. Nếu tệp đã tải xong thì phần dung lượng chưa dùng của gói đang dùng bị bỏ đi.

Ở mọi chế độ, số byte tải được đều là số nguyên (không tải một phần byte).

Hãy tìm số tiền nhỏ nhất Polycarp phải trả để tải xong tệp trong thời gian không quá $T$ mili giây, hoặc cho biết không thể.

Dữ liệu vào

• Dòng 1: ba số nguyên $f$, $T$, $t_0$.
• Dòng 2: ba số nguyên $a_1$, $t_1$, $p_1$.
• Dòng 3: ba số nguyên $a_2$, $t_2$, $p_2$.

Dữ liệu ra

In ra số tiền nhỏ nhất cần trả. Nếu không thể tải xong trong thời gian $T$, in ra $-1$.

Ràng buộc

• $1\le f,T,t_0\le {10}^7$
• $1\le a_1,t_1,p_1,a_2,t_2,p_2\le {10}^7$

Ví dụ