(*                This is a MARTELLO  and TOTH Knapsack Algorithm 

   INPUT	: The associated datafile for this algorithm is called
		  "KnapBackDatafile".

		  "KnapBackDatafile" consists of
		  1.  # of variables, N.
		  2.  array of object profits
                  3. array of object weights
                  4. Total weight limit of the knapsack

		  FIRST NUMBER in "KnapBackDatafile" represents 
		  # of variables, N.

		  SECOND NUMBER is the toal weight limit of the knapsack.

		  THIRD set of data represents object profit if
		  object(variable) i is taken.

	          FOURTH set of data represents object weight of an
		  object.

  Algorithm	: This algorithm is based on ENUMERATION method which is
		  known as MARTELLO  and TOTH method.

		  This algorithm applied to the following knapsack problem

		  max  SUM (Pi*Xi)   i= 1 to N

                  s.t  SUM (Wi*Xi)   <=  V   for i = 1 to N
                       Xi = 0 or 1           for i = 1 to N

                  where Pi = profit of variable i
                        Wi = weight of variable i
                        V  = max weight of knapsack.
                    It is also assumed that the objects(variables) are
                  arrange as
                        P1/W1 >= P2/W2 >= P3/W3 ...>= Pn/Wn

                  Maximum # of objects is set to maxobject = 50.
                  One can modify them according to their needs.

   OUTPUT	: Outputs are
		  1. total profit,
		  2. Total weight left in the knapsack
		  3. Determine which object has been taken.         *)
 

program KnapBack(input,output,KnapBackDatafile,KnapBackOutfile);


const   
        maxobject =     50;

type    CHARFILE        =       file of char;
        ARRN            =       array[1..maxobject] of integer;
        ARRN1		=       array[1..maxobject+1] of integer;


var     KnapBackDatafile        :       CHARFILE;
	KnapBackOutfile		:	CHARFILE;
        N,      Nextint         :       integer;
        P,      W               :       ARRN1;
        X                       :       ARRN;
        V,      PROFIT          :       integer;
        COUNT			:	integer;



procedure Infile (var Nextint   :       integer;
                  var N         :       integer;
                  var P,    W   :       ARRN1;
                  var V         :       integer);

var counter : integer;

begin
  reset(KnapBackDatafile);
  readln(KnapBackDatafile, Nextint);
  N := Nextint;
  readln(KnapBackDatafile, Nextint);
  V := Nextint;
  for counter := 1 to N do
  begin
    read(KnapBackDatafile, Nextint);
    P[counter] := Nextint;
  end;
  readln(KnapBackDatafile);

  for counter := 1 to N do
  begin
    read(KnapBackDatafile, Nextint);
    W[counter] := Nextint;
  end;
  readln(KnapBackDatafile);
end;

procedure KNAPBACKTRACK(
       N           :integer;
   var P,W         :ARRN1;
   var X           :ARRN;
       V           :integer;
   var PROFIT,COUNT:integer);

   var D,I,J,K,L,LL,LIM,M,PP,Q,R,T,WW :integer;
       B,STEP2,STEP4,STEP56,STEP7,StoP:boolean;
       MIN,PD,WD,Y,ZD                 :ARRN;

   procedure WorKvar;
      var J,W1,P1:integer;
   begin                                  (* SAVING CURRENT SOLUTION *)
      for J:=I to L do Y[J]:=1;
      P1:=PP;  PD[I]:=P1;
      W1:=V-WW;  WD[I]:=W1;
      ZD[I]:=L+1;
      for J:=I+1 to L do begin
         P1:=P1-P[J-1];  PD[J]:=P1;
         W1:=W1-W[J-1];  WD[J]:=W1;
         ZD[J]:=L+1
      end;  (* for J *)
      for J:=L+1 to LL do begin
         PD[J]:=0;  WD[J]:=0;  ZD[J]:=J
      end;
      V:=WW;  Q:=Q+PP;
      LL:=L
   end;  (* WorKvar *)

begin                                                   (* MAIN BODY *)
   COUNT:=1;
   PP:=0;  WW:=V;  L:=0;
   while WW >= W[L+1] do begin
      L:=L+1;
      PP:=PP+P[L];  WW:=WW-W[L]
   end;
   StoP:=WW = 0;
   if StoP then begin              (* THE GREEDY SOLUTION IS OPTIMAL *)
      PROFIT:=PP;
      for J:=1 to L do X[J]:=1;
      for J:=L+1 to N do X[J]:=0
   end
   else begin                                      (* INITIALIZATION *)
      R:=V+1;  MIN[N]:=R;
      for J:=N downto 2 do begin
         if W[J] < R then R:=W[J];
         MIN[J-1]:=R
      end;
      P[N+1]:=0;  W[N+1]:=V+1;
      LIM:=PP+trunc(WW*P[L+2]/W[L+2]);
      R:=PP+trunc(P[L+1]-(W[L+1]-WW)*P[L]/W[L]);
      if R > LIM then LIM:=R;
      for J:=1 to N do Y[J]:=0;
      PROFIT:=0;  Q:=0;
      I:=1;  LL:=N;
      STEP2:=false;  STEP4:=true;
      repeat  (* until StoP *)
         while STEP2 do begin     (* STEPS 2, 3 BUILD A NEW SOLUTION *)
            COUNT:=COUNT+1;
            if W[I] <= V then begin                        (* STEP 3 *)
               STEP2:=false;
               PP:=PD[I];  WW:=V-WD[I];
               L:=ZD[I];  B:=true;
               while (L <= N) and B do begin
                  B:=W[L] <= WW;
                  if B then begin
                     PP:=PP+P[L];  WW:=WW-W[L];  L:=L+1
                  end
               end;
               L:=L-1;
               if (WW > 0) and (L < N) then begin
                  STEP56:=PROFIT >= Q+PP+trunc(WW*P[L+1]/W[L+1]);
                  STEP4:=not STEP56
               end
               else begin
                  STEP56:=true;  STEP4:=false;
                  if PROFIT < Q+PP then begin
                     PROFIT:=Q+PP;
                     for J:=1 to I-1 do X[J]:=Y[J];
                     for J:=I to L do X[J]:=1;
                     for J:=L+1 to N do X[J]:=0;
                     StoP:=PROFIT = LIM;
                     STEP56:=not StoP
                  end  (* if PROFIT < Q+PP *)
               end  (* else: WW = 0 or L = N *)
            end  (* if W[I] <= V - STEP 3 *)
            else begin
               STEP56:=PROFIT >= Q+trunc(V*P[I+1]/W[I+1]);
               STEP4:=false;  STEP2:=not STEP56;
               if STEP2 then I:=I+1
            end
         end;  (* while STEP2 *)
         if STEP4 then begin     (* STEP 4 - SAVING CURRENY SOLUTION *)
            WorKvar;
            if L < N-2 then begin
               I:=L+2;
               STEP56:=V < MIN[I-1];
               STEP2:=not STEP56;  STEP7:=false
            end
            else begin
               STEP56:=true;
               if L = N-2 then begin
                  if V >= W[N] then begin
                     Q:=Q+P[N];  V:=V-W[N];  Y[N]:=1
                  end;
                  I:=N-1
               end
               else I:=N
            end;  (* else: L >= N-2 *)
            if STEP56 then begin
                         (* STEP 5 - SAVING CURRENT OPTIMAL SOLUTION *)
               if PROFIT < Q then begin
                                   (* BETTER SOLUTION HAS BEEN FOUND *)
                  PROFIT:=Q;
                  for J:=1 to N do X[J]:=Y[J];
                  StoP:=PROFIT = LIM;
                  STEP56:=not StoP
               end;  (* if PROFIT < Q *)
               if STEP56 and (Y[N] = 1) then begin
                  Q:=Q-P[N];  V:=V+W[N];  Y[N]:=0
               end
            end  (* if STEP56 *)
         end;  (* if STEP4 *)
         if STEP56 then begin           (* STEPS 6, 7 - BACKTRACKING *)
            StoP:=true;  K:=I;
            while StoP and (K > 1) do begin
               K:=K-1;  StoP:=Y[K] = 0
            end;
            STEP7:=not StoP;
            if STEP7 then begin
               R:=V;  Y[K]:=0;
               Q:=Q-P[K];  V:=V+W[K];
               STEP2:=R >= MIN[K];  STEP7:=not STEP2;
               if STEP2 then I:=K+1
               else begin I:=K;  M:=K+1  end
            end;  (* if STEP7 *)
            while STEP7 do begin            (* STEP 7 - SUBSTITUTION *)
               STEP56:=(M > N) or (PROFIT >= Q+trunc(V*P[M]/W[M]));
               STEP7:=not STEP56;  STEP2:=STEP7;  STEP4:=STEP7;
               if STEP7 then begin
                  D:=W[M]-W[K];  T:=R-D;
                  if D = 0 then M:=M+1
                  else
                     if D > 0 then begin
                        if (T < 0) or (PROFIT >= Q+P[M]) then M:=M+1
                        else begin
                           PROFIT:=Q+P[M];
                           for J:=1 to K do X[J]:=Y[J];
                           for J:=K+1 to N do X[J]:=0;
                           X[M]:=1;
                           StoP:=PROFIT = LIM;
                           STEP7:=not StoP;
                           if STEP7 then begin
                              R:=T;  K:=M;  M:=M+1
                           end
                        end  (* else (T < 0) ... *)
                     end  (* if D > 0 *)
                     else begin  (* D < 0 *)
                        if T < MIN[M] then M:=M+1
                        else begin
                           STEP7:=false;
                           STEP56:=Q+P[M]+trunc(T*P[M]/W[M])<=PROFIT;
                           STEP2:= not STEP56;  STEP4:=STEP2;
                           if STEP2 then begin
                              Q:=Q+P[M];  V:=V-W[M];
                              Y[M]:=1;  I:=M+1;
                              PD[M]:=P[M];  WD[M]:=W[M];
                              ZD[M]:=M+1;
                              for J:=M+1 to LL do begin
                                 PD[J]:=0;  WD[J]:=0;  ZD[J]:=J
                              end;
                              LL:=M
                           end  (* if STEP2 *)
                        end  (* else: T >= MIN[M] *)
                     end  (* else: D < 0 *)
               end  (* if STEP7 *)
            end  (* while STEP7 *)
         end  (* if STEP56 *)
      until StoP
   end  (* else: not StoP *)
end;  (* KNAPBACKTRACK *)



procedure Outfile(N	:	integer;
		  X	:  	ARRN;
		  PROFIT :	integer;
		  COUNT	 :	integer);

var counter : integer;

begin
  rewrite(KnapBackOutfile);
  writeln(KnapBackOutfile,'  optimal solution for the values in X array  = ',PROFIT);
  writeln(KnapBackOutfile,'  number of forward moves perfomed =',COUNT);
  for counter := 1 to N  do
    writeln(KnapBackOutfile,'  X',counter:2,' =',X[counter]);
end;


begin  (* main *)
  Infile(Nextint,N,P,W,V);
  KNAPBACKTRACK(N,P,W,X,V,PROFIT,COUNT);
  Outfile(N,X,PROFIT,COUNT);
end.