Downloading B++

잘 알려진 온라인 프로그래밍 대회 Codehorses Round 2017이 시작되기까지 Only T밀리초가 남았다.

Polycarp는 대회에 참가하기 위해 B++ 컴파일러를 다운로드해야 한다. 파일 크기는 f바이트이다.

Polycarp의 인터넷 요금제에서는 t0밀리초마다 한 바이트의 속도로 데이터를 다운로드할 수 있다. 이 요금제는 이미 선불로 결제되어 있으며, 이를 사용해도 Polycarp에게 비용이 발생하지 않는다. 또한 인터넷 서비스 제공자는 다음 두 가지 추가 패키지를 제공한다.

• 패키지 요금으로 p1벌을 지불하고, t1밀리초마다 한 바이트의 속도로 a1바이트를 다운로드한다.
• 패키지 요금으로 p2벌을 지불하고, t2밀리초마다 한 바이트의 속도로 a2바이트를 다운로드한다.

Polycarp는 어떤 패키지든 여러 번 구매할 수 있다. 패키지를 구매하면 사용 전에 그 가격(p1 또는 p2)을 선불로 지불한다. 패키지를 구매한 뒤에는 패키지의 데이터 한도를 완전히 사용할 때까지 해당 패키지가 일반 요금제를 대체한다. 패키지를 모두 사용한 뒤에는 시간을 전혀 잃지 않고 즉시 새 패키지를 구매하거나 일반 요금제로 전환할 수 있다. 패키지를 사용하는 동안에는 다른 패키지를 구매하거나 일반 인터넷 요금제로 되돌아갈 수 없다.

크기가 f바이트인 파일을 T밀리초 이내에 다운로드하기 위해 Polycarp가 지출해야 하는 최소 금액을 구한다.

기술적인 이유로 Polycarp는 일반 요금제와 두 패키지에서 모두 정수 바이트만 다운로드할 수 있다는 점에 유의한다. I.e. 세 가지 다운로드 방식 각각에서 다운로드하는 바이트 수는 정수여야 한다. 즉, Polycarp는 일반 요금제 또는 두 패키지를 사용하여 한 바이트의 일부만 다운로드할 수 없다.

첫 번째 줄에는 세 정수 f, T, t0 (1 ≤ f, T, t0 ≤ 107)가 주어진다. 이들은 각각 다운로드할 파일의 크기(바이트), 파일을 다운로드할 수 있는 최대 시간(밀리초), 일반 인터넷 요금제로 한 바이트를 다운로드하는 데 걸리는 밀리초 수를 나타낸다.

두 번째 줄에는 첫 번째 추가 패키지에 대한 설명이 주어진다. 이 줄에는 세 정수 a1, t1, p1 (1 ≤ a1, t1, p1 ≤ 107)가 주어지며, a1는 다운로드할 수 있는 데이터의 최대 크기(바이트), t1는 한 바이트를 다운로드하는 데 걸리는 시간(밀리초), p1는 패키지 가격(벌)이다.

세 번째 줄에는 두 번째 추가 패키지에 대한 설명이 주어진다. 이 줄에는 세 정수 a2, t2, p2 (1 ≤ a2, t2, p2 ≤ 107)가 주어지며, a2는 다운로드할 수 있는 데이터의 최대 크기(바이트), t2는 한 바이트를 다운로드하는 데 걸리는 시간(밀리초), p2는 패키지 가격(벌)이다.

Polycarp는 어떤 패키지든 여러 번 구매할 수 있다. 패키지를 구매하면 패키지의 데이터 한도를 완전히 사용할 때까지 해당 패키지가 일반 요금제를 대체한다. 패키지를 사용하는 동안에는 다른 패키지를 구매하거나 일반 인터넷 요금제로 되돌아갈 수 없다.

B++ 컴파일러를 T밀리초 이내에 다운로드하기 위해 Polycarp가 지불해야 하는 최소 금액을 출력한다. 해답이 없다면 유일한 정수 -1을 출력한다.

첫 번째 예제에서 Polycarp는 첫 번째 추가 패키지를 5번 구매하고 두 번째 추가 패키지는 구매하지 않아야 한다. 그는 120바이트를 (of total 26·5 = 130 bytes) 120·8 = 960밀리초 만에 (960 ≤ 964) 다운로드한다. 여기에 8·5 = 40벌을 지출한다.

두 번째 예제에서 Polycarp에게는 10바이트를 다운로드할 시간이 충분하다. 여기에는 10·20 = 200밀리초가 걸리며, 이는 다운로드 시간의 상한과 같다.

세 번째 예제에서 Polycarp는 첫 번째 추가 패키지 하나와 두 번째 추가 패키지 하나를 구매해야 한다.

네 번째 예제에서 Polycarp는 파일을 제시간에 다운로드할 방법이 없다.