Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_15_12 - World of Bajtcraft

Po raz kolejny uruchamiasz swoją ulubioną grę: World of Bajtcraft. Jako wytrawny gracz postanawiasz spróbować wygrać w najtrudniejszy możliwy sposób - poprzez zwycięstwo kulturalne. Polega ono na tym, że wygrywa gracz, który jako pierwszy zbuduje jeden z cudów świata.

Nie jest to jednak takie proste. Trzeba najpierw uzbierać ogromną ilość surowców. Zakładając, że skupiasz się tylko i wyłącznie na zbieraniu surowców, policz w jakim czasie jesteś w stanie uzbierać potrzebne materiały (oczywiście chcesz to zrobić jak najszybciej).

Na początku gry masz do dyspozycji jednego robotnika. Robotnik pracuje w kopalni i co minutę przynosi k surowców. Możesz wyprodukować nowego robotnika, ale to będzie kosztowało s surowców i trwało m minut (żeby rozpocząć produkcje nowego robotnika musisz mieć w banku dostępne wymagane surowce). Możesz produkować tylko jednego robotnika w danym momencie (nawet jak masz zasoby na kupno kilku na raz). Twój cel, to jak najszybsze uzbieranie g surowców.

Celem jest posiadanie w banku g surowców. Nie mówimy tutaj o sumarycznej liczbie surowców, jakie uzbieraliśmy przez cały czas trwania rozgrywki.

Wejście

Na wejściu znajduje się t - liczba testów (t ≤ 2000)

Każdy test składa się z 4 wartości: k, s, m, g (0 < k, s, m, g ≤ 105) opisanych w treści zadania.

Wyjście

Ile co najmniej minut potrzeba na uzbieranie wymaganych surowców.

Przykład

Wejście:

3
2 3 4 10
2 3 4 20
1 1 1 100000

Wyjście:

5
9
449

Dodane przez:Grzegorz Spryszyński
Data dodania:2022-04-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.