(*          This is a Knapsack Algorithm base on Approximation method.

   INPUT	: The associated datafile for Approximation problem is
		  called "KnapAppxDatafile".

		  "KnapAppxDatafile" 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 "KnapAppxDatafile" is the # 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 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.Determine which object has been taken.

  NOTE	 	: All the solutions obtained from this algorithm were
		  within 2% of the optimal solution.                   *)


program KnapApproximation(input,output,KnapAppxDatafile,KnapAppxOutfile);


const	INF	=	1000;
        maxobject =     50;
        CONSTANT  =     0.33333;

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

var     KnapAppxDatafile 	:	CHARFILE;
	KnapAppxOutfile		:	CHARFILE;
        N,   	Nextint		:	integer;
        P,	W		:	ARRN;
	X			:	ARRN;
	V,	PROFIT		:	integer;
        EPS			:	real;



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

var counter : integer;

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



procedure KNAPAPPROX(
       N       :integer;
   var P,W,X   :ARRN;
   var V,PROFIT:integer;
   var EPS     :real);

   var I,J,K,L,MAXP1,MAXP2,MAXP3,PP,Q,R,S,U,VV:integer;

   procedure LB(G,H:integer;var Q,U:integer);
      (* LB FINDS PROFIT Q and RESIDUAL WEIGHT OF GREEDY TYPE
        SOLUTION WHICH IS ASSUMED to CONTAIN OBJECTS G and H *)
      var K:integer;
   begin
      K:=0;
      repeat
         K:=K+1;
         if (K <> G) and (K <> H) and (W[K] <= U) then begin
            Q:=Q+P[K];  U:=U-W[K]
         end
      until K=N
   end;  (* LOWER BOUND *)

   procedure MAX;
      (* MAX UPDATES MAXP1, MAXP2, and MAXP3: LARGEST, SECOND
        and THIRD LARGEST ELEMENTS OF THE PROFIT VECtoR *)
   begin
      if P[I] > MAXP1 then begin
         MAXP3:=MAXP2;  MAXP2:=MAXP1;  MAXP1:=P[I]
      end
      else
         if P[I] > MAXP2 then begin MAXP3:=MAXP2;  MAXP2:=P[I] end
         else if P[I] > MAXP3 then MAXP3:=P[I]
   end;  (* MAX *)

begin                                                   (* MAIN BODY *)
   I:=1;  U:=V;  PROFIT:=0;
   MAXP1:=0;  MAXP2:=0;  MAXP3:=0;
   while W[I] <= U do begin               (* FINDING GREEDY SOLUTION *)
      U:=U-W[I];  MAX;  X[I]:=1;
      PROFIT:=PROFIT+P[I];
      I:=I+1
   end;
   I:=I-1;  S:=I;
   repeat
      I:=I+1;
      if W[I] <= U then begin
         U:=U-W[I];  X[I]:=1;  PROFIT:=PROFIT+P[I]
      end
      else X[I]:=0;
      MAX
   until I=N;
   Q:=PROFIT;
                                    (* ONE ELEMENT SUBSETS OF OBJECT *)
   K:=0;  L:=0;                (* K and L IDENTifY THE OBJECTS WHICH *)
   for I:=S to N do               (* ARE ASSUMED to BE IN A SOLUTION *)
      if X[I] <> 1 then begin
         VV:=V-W[I];  PP:=P[I];
         LB(I,I,PP,VV);
         if PP > PROFIT then begin PROFIT:=PP;  K:=I end
      end;  (*if X[I] <> 1, for I *)
   R:=S;                           (* TWO ELEMENT SUBSETS OF OBJECTS *)
   for I:=1 to N-1 do begin
      if I > S then R:=I;
      for J:=R+1 to N do begin
         VV:=V-W[I]-W[J];
         if VV >= 0 then begin
            PP:=P[I]+P[J];
            LB(I,J,PP,VV);
            if PP > PROFIT then begin PROFIT:=PP;  K:=I;  L:=J end
         end
      end  (* for J *)
   end;  (* for I *)
   if PROFIT > Q then begin
      if K > 0 then begin V:=V-W[K];  X[K]:=1  end;
      if L > 0 then begin V:=V-W[L];  X[L]:=1  end;
      for I:=1 to N do
         if (I <> K) and (I <> L) then
            if W[I] <= V then begin X[I]:=1;  V:=V-W[I] end
            else X[I]:=0
   end;  (* if PROFIT > Q *)
   EPS:=MAXP3/PROFIT;
   if EPS > 0.33333 then EPS:=0.33333
end;  (* KNAPAPPROX *)



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

var counter : integer;

begin
  rewrite(KnapAppxOutfile);
  writeln (KnapAppxOutfile,' PROFIT is  ',PROFIT,'  with  ');
  for counter := 1 to N do
  begin
    writeln(KnapAppxOutfile,'  X',counter:2,' = ',X[counter]);
  end;
end;

begin (*  main *)
  EPS := CONSTANT;
  Infile(Nextint,N,P,W,V);
  KNAPAPPROX(N,P,W,X,V,PROFIT,EPS);
  Outfile(N,PROFIT,X);
end.