(* 		         This is a  Knapsack Algorithm
  
   INPUT	: The associated datafile for Reduction problem is called
		  "KnapRedDatafile".

		  "KnapRedDatafile" 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 "KnapRedDatafile" 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	: Since Knapack problem is NP-hard, REDUCTION method is
		  used to solve knapsack problem.

		  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. Check whether an optimal solution or a partial
		     feasible  solution has been found.
		  2. Output its total profit.
		  3. Total weight left in the knapsack.
		  4. Determine which object has been taken.       

   Time		: The running of this REDUCTION algorithm is O(N^2)    *)

	          


program KnapReduction(input,output,KnapRedDatafile,KnapRedOutfile);


const   INF     =       1000;
        maxobject =     50;

type    CHARFILE        =       file of char;
        ARRN            =       array[1..maxobject] of integer;
        ARR0N           =       array[0..maxobject] of integer;
        ARR0N2          =       array[0..maxobject+2] of integer;

var     KnapRedDatafile        :       CHARFILE;
        KnapRedOutfile	       :       CHARFILE;
        N,      Nextint         :       integer;
        P,      W               :       ARR0N2;
        X                       :       ARRN;
        V,      PROFIT          :       integer;
        OPTSOL                  :       boolean;


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

var counter : integer;

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

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


procedure KNAPRED(
       N       :integer;
   var P,W     :ARR0N2;
   var X       :ARRN;
   var V,PROFIT:integer;
       INF     :integer;
   var OPTSOL  :boolean);

   var I,J,LB,PP,PPP,Q,QQ,R,S,VV,Y,Z,WW,WWW:integer;
       B                                   :boolean;
       PR,WR                               :ARRN;
       UB                                  :ARR0N;

   procedure AUGMENT(I,K:integer);
      (* THE procedure AUGMENTS A PARTIAL SOLUTION WHICH WEIGHS VV
        and HAS PROFIT Q, STARTING WITH OBJECT K+1 and TRYING to
        ADD AS MANY OBJECTS AS POSSIBLE (EXCEPT THE I-TH OBJECT)
        WHICH FOLLOW OBJECT K. *)
      var KK,VVV:integer;
   begin
      KK:=K+1;  VVV:=VV;  QQ:=Q;
      while KK <= N do begin
         if (VVV >= W[KK]) and (KK <> I) then begin
            VVV:=VVV-W[KK];  QQ:=QQ+P[KK]
         end;
         KK:=KK+1
      end
   end;  (* AUGMENT *)

   procedure UBO(I:integer);
      (* UBO(I) FINDS WEIGHT VV and PROFIT Q OF THE GREEDY SOLUTION
        OBTAINED BY ASSUMING X[I]=0, WHERE I <= R, and TAKING AS
        MANY AS POSSIBLE CONSECUTIVE OBJECTS. UPON EXIT, QQ IS THE
        PROFIT OF THE GREEDY SOLUTION AUGMENT BY procedure AUGMENT. *)
      var WI:integer;
          BB:boolean;
   begin
      WI:=W[I];  S:=R-1;  BB:=true;
      while (S <= N) and BB do
         if WI >= WR[S] then S:=S+1
         else BB:=false;
      S:=S-1;  VV:=WI-WR[S];  Q:=PR[S]-P[I];
      AUGMENT(I,S)
   end;  (* UBO *)

   procedure UB1(I:integer);
      (* UB1(I) FINDS WEIGHT VV and PROFIT Q OF THE GREEDY SOLUTION
        OBTAINED BY ASSUMING X[I]=1, WHERE R <= I, and TAKING AS MANY
        AS POSSIBLE CONSECUTIVE OBJECTS. UPON EXIT, QQ IS THE PROFIT
        OF THE GREEDY SOLUTION AUGMENT BY procedure AUGMENT. *)
      var WI:integer;
   begin
      WI:=W[I];  S:=R;
      while WR[S] < WI do S:=S-1;
      VV:=WR[S]-WI;  Q:=PR[S]+P[I];
      AUGMENT(I,R)
   end; (* UB1 *)

begin                                                   (* MAIN BODY *)
   PP:=0;  WW:=0;  R:=1;
   while WW+W[R] < V do begin
      WW:=WW+W[R];  PP:=PP+P[R];  R:=R+1
   end;
   WW:=V-WW;
   if WW = W[R] then begin         (* THE GREEDY SOLUTION IS OPTIMAL *)
      V:=0;  PROFIT:=0;
      for I:=1 to R do begin
         X[I]:=1;  PROFIT:=PROFIT+P[I]
      end;
      for I:=R+1 to N do X[I]:=0;
      OPTSOL:=true
   end  (* if WW = W[R] - OPTIMAL SOLUTION *)
   else begin                                 (* REDUCTION ALGorITHM *)
      W[0]:=1;  W[N+1]:=INF;  W[N+2]:=INF;
      P[0]:=P[1];  P[N+1]:=0;  P[N+2]:=0;
      VV:=WW;  Q:=PP;
      AUGMENT(0,R-1);
      LB:=QQ;
      WWW:=-WW;  PPP:=PP;
      WR[R-1]:=-WW;  PR[R-1]:=PP;
      for I:=R to N do begin
         WWW:=WWW+W[I];  WR[I]:=WWW;
         PPP:=PPP+P[I];  PR[I]:=PPP
      end;
      WWW:=WW+W[R-1];  PPP:=PP-P[R-1];
      for I:=R-2 downto 1 do begin
         WWW:=WWW+W[I];  WR[I]:=WWW;
         PPP:=PPP-P[I];  PR[I]:=PPP
      end;
      I:=1;  J:=-1;
      B:=true;
      repeat  (* until I > N *)      (* FINDING UPPER and LOWER BOUNDS *)
         if B then UBO(I)
         else begin UB1(I);  S:=S-1 end;
         Y:=trunc(VV*P[S+2]/W[S+2]);
         Z:=trunc(P[S+1]-(W[S+1]-VV)*(P[S]/W[S]));
         if Z > Y then Y:=Z;
         UB[I+J]:=Q+Y;
         if QQ > LB then LB:=QQ;
         if (I = R) and B then begin
            B:=false;  J:=0;
            WR[R-1]:=WW+W[R-1];  WR[R]:=WW;
            PR[R-1]:=PP-P[R-1];  PR[R]:=PP
         end
         else I:=I+1
      until I > N;
      PROFIT:=0;  J:=0;
      for I:=1 to N do X[I]:=-1;
      for I:=1 to R do
         if UB[I-1] < LB then begin
            J:=J+1;  X[I]:=1;  V:=V-W[I];
            PROFIT:=PROFIT+P[I]
         end;
      I:=1;
      while I <= N do begin
         if (W[I] > V) and (X[I] = -1) then begin
            X[I]:=0;  J:=J+1
         end;
         I:=I+1
      end;  (* while I <= N *)
      I:=R;
      while (I <= N) and (J < N) do begin
         if UB[I] < LB then begin
            X[I]:=0;  J:=J+1
         end;
         I:=I+1
      end;  (* while (I <= N) ... *)
      OPTSOL:=J = N;
      if not OPTSOL then begin
         WW:=0;
         for I:=1 to N do if X[I] = -1 then WW:=WW+W[I];
         OPTSOL:=WW=V;
         if OPTSOL then begin
            V:=0;
            for I:=1 to N do
               if X[I] = -1 then begin
                  X[I]:=1;  PROFIT:=PROFIT+P[I]
               end
         end  (* if OPTSOL *)
      end  (* if not OPTSOL - J < N *)
   end  (* else: WW <> W[R] *)
end;  (* KNAPRED *)



procedure Outfile(N   : integer;
                  V   : integer;
                  X   : ARRN;
                  PROFIT : integer;
                  OPTSOL : boolean);

var counter : integer;

begin
  rewrite(KnapRedOutfile);
  writeln(KnapRedOutfile,'OPTSOL =  ',OPTSOL);
  writeln(KnapRedOutfile,' Profit of Partial Assignment is ',PROFIT);
  for counter := 1 to N do
    writeln(KnapRedOutfile,'  X',counter:2,' = ',X[counter]);
  writeln(KnapRedOutfile);
  writeln(KnapRedOutfile,'  total weight limit after reduced problem is ',V);
end;



begin (*  main *)
  Infile(Nextint,N,P,W,V);
  KNAPRED(N,P,W,X,V,PROFIT,INF,OPTSOL);
  Outfile(N,V,X,PROFIT,OPTSOL);
end.