Mining

---

Time limit: 1 Seconds   Memory limit: 32768K  
Total Submit: 1459   Accepted Submit: 241  

---

  A mining base needs to build some robots to collect at least 10000 units of resource. Each robot will start from the base, reach the diggings in S minutes, work for W minutes, and then take C units of resource back to the base in S minutes.
  To speed up this procedure, K robots will be built at the base. It takes M minutes to produce one robot. A robot will be set to start working immediately after it is built, and producing the next robot will be on line right after. This procedure continues untill all the robots are built.
  Due to the limitation of the mining equipments, there can be only one robot digging at the working area. That is, it is only after the currently working robot finishes its collecting work and starts getting back to the base that the next robot can work at the diggings.
  Now it is your job to write a program to simulate this procedure, and find out how many minutes it will take to collect at least 10000 units of resource.

Input
There are several lines of input. Each line contains a test case which consists of 5 integers, namely S, W, C, K, and M.

Output
For each test case, you are asked to output an integer t, which is the number of minutes taken to collect at least 10000 units of resource.

Sample Input:

10 20 10 1 5

Sample Output:

40005

Program Zoj_1200_Mpq;

Const Maxn=10000;

var
  s,w,c,m,Len,Ans:Longint;
  Heap:array[0..Maxn] of longint;

procedure init;
var
  i:integer;
begin
  Ans:=0;
  readln(s,w,c,Len,m);
  if 9999 div c+1<Len then Len:=9999 div c+1;
  for i:=1 to Len do
    Heap[i]:=i*m+s;
end;

procedure solve;
var
  i,j:integer;
begin
  if heap[1]>ans then ans:=heap[1];
  ans:=ans+w;
  inc(heap[1],2*s+w);
  i:=1; j:=i*2;
  while j<=Len do
  begin
    if (j<len) and (heap[j+1]<heap[j]) then inc(j);
    if heap[i]>heap[j] then
    begin
      heap[0]:=heap[i];
      heap[i]:=heap[j];
      heap[j]:=heap[0];
      i:=j;
      j:=j*2;
    end else break;
  end;
end;

procedure work;
var
  i:integer;
begin
  for i:=1 to 9999 div c+1 do solve;
  writeln(ans+s);
end;

begin
  while not eof do
  begin
    init;
    work;
  end;
end.