/* 

  Cutting stock problem (two stage) in Picat.

  From https://en.wikipedia.org/wiki/Cutting_stock_problem
  """
  A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600 mm wide. 
  The following 13 items must be cut, in the table below.

  The important thing about this kind of problem is that many different product units can be made 
  from the same master roll, and the number of possible combinations is itself very large, in general, 
  and not trivial to enumerate.

  The problem therefore is to find an optimum set of patterns of making product rolls from the master 
  roll, such that the demand is satisfied and waste is minimized.

  Width	#Items
  1380	22
  1520	25
  1560	12
  1710	14
  1820	18
  1880	18
  1930	20
  2000	10
  2050	12
  2100	14
  2140	16
  2150	18
  2200	20

  Bounds and checks
  A simple lower bound is obtained by dividing the total amount of product by the size of each master roll. 
  The total product required is 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm. Each master roll is 5600mm, 
  requiring a minimum of 72.7 rolls, which means 73 rolls or more are required.

  Solution

  There are 308 possible patterns for this small instance. The optimal answer requires 73 master rolls and 
  has 0.401% waste; it can be shown computationally that in this case the minimum number of patterns with 
  this level of waste is 10. It can also be computed that 19 different such solutions exist, each with 
  10 patterns and a waste of 0.401%, of which one such solution is shown below and in the picture:
  """

  CP and SAT quickly calculate the 308 patterns (first stage), MIP and SMT are quite slow.
  On the other hand, given the pregenerated patterns MIP and SMT are fast on solving 
  the main problem, but on this stage both CP and SAT are very slow.


  * Time to generate the patterns

    All times are system times since MIP and SMT use external programs.

    Solver    Time to generate the patterns
    ---------------------------------------------------------
    SAT         3.755s
    CP          0.051s (solve time 0.001s)
    MIP        75.4s
    SMT/z3     21.7s
    SMT/cvc4   39.3s

    CP is the winner here.

  * Solve time using precalculated patterns

    Solver    Minimizing #rolls (73)   Minimizing waste (1040)
    ---------------------------------------------------------
    SAT       >5min                    >5min
    CP        >5min                    >5min                 
    MIP       0.130s(*)                 0.148s(*)
    SMT/z3    0.461s                    1.404s
    SMT/cvc4  35.101s                   2.11s
  
    CP (inout/split) finds the optimal value of waster (1040) in some seconds,
    but then it takes "forever" to prove optimality.

    Here MIP is the winner.

    I'm surprised that SMT - especially z3 - is so fast when using the
    precalculated patterns. And that SAT is so slow.


  Total winner for the two stage problem: generating patterns + solving the main problem:
   - minimizinc rolls: SMT/z3: 22,02s
   - minimizinc waste: SMT/z3: 22.7s

  For this problem it would be great to be able to use different solvers
  for the two stages, i.e. CP for generating the patterns and MIP for solving the
  main problem.
 

  Here is smt/z3's solution minimizing the number of rolls:

    patternsLen = 308
    [totalWidth = 407160,minRolls = 73]
    rolls = 73
    waste = 1640
    numPatterns = 13
    [i = 2,x = 1,pattern = [0,1,0,0,0,1,0,0,0,0,0,0,1]]
    [i = 3,x = 7,pattern = [0,0,0,1,0,1,0,1,0,0,0,0,0]]
    [i = 6,x = 14,pattern = [0,1,0,0,0,0,1,0,0,0,1,0,0]]
    [i = 7,x = 2,pattern = [0,0,0,0,1,2,0,0,0,0,0,0,0]]
    [i = 10,x = 12,pattern = [0,0,1,0,1,0,0,0,0,0,0,0,1]]
    [i = 11,x = 7,pattern = [1,0,0,0,0,0,0,0,0,2,0,0,0]]
    [i = 12,x = 12,pattern = [1,0,0,0,0,0,0,0,1,0,0,1,0]]
    [i = 13,x = 3,pattern = [1,0,0,0,0,0,0,1,0,0,0,0,1]]
    [i = 15,x = 3,pattern = [0,0,0,1,0,0,2,0,0,0,0,0,0]]
    [i = 16,x = 2,pattern = [0,0,0,2,0,0,0,0,0,0,0,1,0]]
    [i = 22,x = 4,pattern = [0,1,0,0,0,1,0,0,0,0,0,1,0]]
    [i = 25,x = 2,pattern = [0,1,0,0,0,1,0,0,0,0,1,0,0]]
    [i = 26,x = 4,pattern = [0,1,0,0,1,0,0,0,0,0,0,0,1]]

  And for minimizing the waste:
    patternsLen = 308
    [totalWidth = 407160,minRolls = 73]
    rolls = 104
    waste = 1040
    numPatterns = 9
    [i = 1,x = 20,pattern = [0,1,0,0,0,0,1,0,0,0,0,1,0]]
    [i = 2,x = 20,pattern = [0,1,0,0,0,1,0,0,0,0,0,0,1]]
    [i = 3,x = 8,pattern = [0,0,0,1,0,1,0,1,0,0,0,0,0]]
    [i = 6,x = 16,pattern = [0,1,0,0,0,0,1,0,0,0,1,0,0]]
    [i = 8,x = 6,pattern = [0,0,0,1,1,0,0,0,1,0,0,0,0]]
    [i = 10,x = 12,pattern = [0,0,1,0,1,0,0,0,0,0,0,0,1]]
    [i = 11,x = 14,pattern = [1,0,0,0,0,0,0,0,0,2,0,0,0]]
    [i = 12,x = 6,pattern = [1,0,0,0,0,0,0,0,1,0,0,1,0]]
    [i = 13,x = 2,pattern = [1,0,0,0,0,0,0,1,0,0,0,0,1]]


  This model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

% import sat. 
% import cp. 
% import mip. 
import smt. 

main => go.

%
% Solve the main problem (with pregenerated patterns).
%
go ?=>
  nolog,
  master_width(MasterWidth), % width of master rolls
  demand(Demand),
  
  % Type = rolls,
  Type = waste,

  GeneratePatterns = false,

  println(type=Type),

  % Generate patterns
  if GeneratePatterns then
    DemandWidths = [Demand[I,1] : I in 1..Demand.len],
    time2([Patterns,Wastes] = patterns(MasterWidth,DemandWidths)),
  else 
    % The generated patterns and wastes
    patterns(Patterns),
    wastes(Wastes)
  end,

  PLen = Patterns.len,
  println(patternsLen=PLen),

  MaxX = 20, % domain of X: 0..MaxX

  if Type == rolls then
    cutting_stock(MasterWidth,Demand,Patterns,Wastes,MaxX,Type, X,Rolls,Waste,Rolls)
  else
    cutting_stock(MasterWidth,Demand,Patterns,Wastes,MaxX,Type, X,Rolls,Waste,Waste)  
  end,
  % println(x=X),
  println(x=[[P,X[P]] : P in 1..PLen, X[P] > 0]),  
  println(rolls=Rolls),
  println(waste=Waste),  
  println(numPatterns=sum([1: I in 1..PLen, X[I] > 0])),
  foreach(I in 1..PLen)
    if X[I] > 0 then
      println([i=I,x=X[I],pattern=Patterns[I]])
    end
  end,

  nl.
go => true.  

%
% All optimal solutions (with pre generated patterns).
%
go2 ?=>
  nolog,
  master_width(MasterWidth), % width of master rolls
  demand(Demand),
  Type = rolls,
  % Type = waste,

  println(type=Type),

  % The generated patterns and wastes
  patterns(Patterns),
  wastes(Wastes),
  PLen = Patterns.len,

  MaxX = 20, % domain of X: 0..MaxX
  if Type == rolls then
    println(optRools=Rolls),  
    cutting_stock(MasterWidth,Demand,Patterns,Wastes,MaxX,Type, _,Rolls,Waste,Rolls),
    Z = Rolls
  else
    println(optWaste=Waste),
    cutting_stock(MasterWidth,Demand,Patterns,Wastes,MaxX,Type, _,Rolls,Waste,Waste),
    Z = Waste
  end,

  println("All optimal solutions:"),
  
  cutting_stock(MasterWidth,Demand,Patterns,Wastes,MaxX,Type, X,Rolls,Waste,Z),
  println(z=Z),
  % println(x=X),
  println(x=[[P,X[P]] : P in 1..PLen, X[P] > 0]),  
  println(rolls=Rolls),
  println(waste=Waste),
  foreach(I in 1..PLen)
    if X[I] > 0 then
      println([i=I,x=X[I],pattern=Patterns[I]])
    end
  end,
  NumPatterns = sum([1: I in 1..PLen, X[I] > 0]),
  println(numPatterns=NumPatterns),
  nl,
  fail,

  nl.
go2 => true.  


%
% Generate the patterns.
%
go3 ?=>
  nolog,
  master_width(MasterWidth),
  demand(Demand),
  N = Demand.len,

  DemandWidths = [Demand[I,1] : I in 1..N],
  time2([Patterns,Wastes] = patterns(MasterWidth,DemandWidths)),
  println(patterns=Patterns),
  println(wastes=Wastes),
  println(len=Patterns.len),
  nl.
go3 => true.


%
% Solve the custting stock problem.
%
% Is there a way to reduce the upper limit of Waste?
%
cutting_stock(MasterWidth,Demand,Patterns,Wastes,MaxX,Type, X,Rolls,Waste,Z) => 
  N = Demand.len,
  
  TotalWidth = sum([Demand[I,1]*Demand[I,2] : I in 1..N]),
  MinRolls = ceiling(TotalWidth/MasterWidth),
  println([totalWidth=TotalWidth,minRolls=MinRolls]),

  PLen = Patterns.len,

  % How many of each pattern should be used?
  X = new_list(PLen),
  X :: 0..MaxX, 

  foreach(I in 1..N)
    % exactly the number of demands:
    % sum([X[P]*Patterns[P,I] : P in 1..PLen]) #= Demand[I,2]
    % at least the number of demands:
    sum([X[P]*Patterns[P,I] : P in 1..PLen]) #>= Demand[I,2]    
  end,

  Rolls #= sum(X),
  Rolls #>= MinRolls,
  Waste #= sum([X[J]*Wastes[J] : J in 1..PLen]),

  println(rolls=Rolls),
  println(waste=Waste),
  
  if Type == rolls then 
    Z #= Rolls
  elseif Type == waste then
    Z #= Waste
  else
    println("Wrong type"=Type),
    fail
  end,

  Vars = X ++ [Rolls,Waste],

  if var(Z) then
    solve($[min(Z),inout,split,report(printf("z:%d\n",Z))],Vars) % waste
    % solve($[min(Z),ff,split,report(printf("z:%d\n",Z))],Vars) % rolls 
  else
    solve($[degree,split],Vars)
  end.


%
% Generate all the possible patterns
%
patterns(MasterWidth,Widths) = [PatternsS,WastesS] =>
  N = Widths.len,
  X = new_list(N),
  X :: 0..10,
  Z #= sum([X[I]*Widths[I] : I in 1..N]),
  Z #<= MasterWidth,
  Z #> 0,
  
  All = solve_all($[],X),
  Patterns = [],
  foreach(Pattern in All)
    S = sum([Widths[I]*Pattern[I] : I in 1..N]),
    Waste = MasterWidth - S,
    Patterns := Patterns ++ [[Waste,Pattern]]
  end,
  % Sort the patterns
  % PatternsSorted = Patterns.sort,
  PatternsSorted = Patterns, % or not
  PatternsS = [P[2] : P in PatternsSorted],
  WastesS = [P[1] : P in PatternsSorted].


master_width(5600).
demand(Demand) =>
  Demand = [[1380,22],
            [1520,25],
            [1560,12],
            [1710,14],
            [1820,18],
            [1880,18],
            [1930,20],
            [2000,10],
            [2050,12],
            [2100,14],
            [2140,16],
            [2150,18],
            [2200,20]].


%
% The patterns (generated by patterns/2.
%
patterns([[0,1,0,0,0,0,1,0,0,0,0,1,0],[0,1,0,0,0,1,0,0,0,0,0,0,1],[0,0,0,1,0,1,0,1,0,0,0,0,0],[0,0,1,0,0,0,1,0,0,1,0,0,0],[0,0,1,0,0,1,0,0,0,0,0,1,0],[0,1,0,0,0,0,1,0,0,0,1,0,0],[0,0,0,0,1,2,0,0,0,0,0,0,0],[0,0,0,1,1,0,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,0,0,1,0,0],[0,0,1,0,1,0,0,0,0,0,0,0,1],[1,0,0,0,0,0,0,0,0,2,0,0,0],[1,0,0,0,0,0,0,0,1,0,0,1,0],[1,0,0,0,0,0,0,1,0,0,0,0,1],[0,0,0,0,2,0,1,0,0,0,0,0,0],[0,0,0,1,0,0,2,0,0,0,0,0,0],[0,0,0,2,0,0,0,0,0,0,0,1,0],[0,1,0,0,0,0,0,1,1,0,0,0,0],[1,0,0,0,0,0,0,0,1,0,1,0,0],[0,0,0,2,0,0,0,0,0,0,1,0,0],[0,0,1,0,0,0,0,2,0,0,0,0,0],[0,1,0,0,0,0,1,0,0,1,0,0,0],[0,1,0,0,0,1,0,0,0,0,0,1,0],[0,0,1,0,0,0,1,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,0,1,0,0,0],[0,1,0,0,0,1,0,0,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,0,0,1],[0,0,0,1,1,0,0,1,0,0,0,0,0],[0,0,1,0,1,0,0,0,0,0,0,1,0],[1,0,0,0,0,0,0,0,1,1,0,0,0],[1,0,0,0,0,0,0,1,0,0,0,1,0],[0,0,0,0,2,1,0,0,0,0,0,0,0],[0,0,0,1,0,1,1,0,0,0,0,0,0],[0,0,0,2,0,0,0,0,0,1,0,0,0],[0,0,1,0,1,0,0,0,0,0,1,0,0],[0,1,0,0,0,0,0,2,0,0,0,0,0],[1,0,0,0,0,0,0,1,0,0,1,0,0],[4,0,0,0,0,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,1,0,0,0,0,0,1],[0,1,0,0,0,0,1,0,1,0,0,0,0],[0,1,0,0,0,1,0,0,0,1,0,0,0],[0,0,1,0,0,0,1,1,0,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,0,0],[0,1,0,0,1,0,0,0,0,0,0,1,0],[0,0,1,0,1,0,0,0,0,1,0,0,0],[0,1,0,0,1,0,0,0,0,0,1,0,0],[1,0,0,0,0,0,0,0,2,0,0,0,0],[1,0,0,0,0,0,0,1,0,1,0,0,0],[0,0,0,1,0,2,0,0,0,0,0,0,0],[0,0,0,2,0,0,0,0,1,0,0,0,0],[0,0,1,1,0,0,0,0,0,0,0,0,1],[0,0,0,0,3,0,0,0,0,0,0,0,0],[0,0,0,1,1,0,1,0,0,0,0,0,0],[1,0,0,0,0,0,1,0,0,0,0,1,0],[1,0,0,0,0,1,0,0,0,0,0,0,1],[0,1,0,0,0,0,1,1,0,0,0,0,0],[0,1,0,0,0,1,0,0,1,0,0,0,0],[1,0,0,0,0,0,1,0,0,0,1,0,0],[0,0,1,0,0,1,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,0,0,1,0,0,0],[0,0,1,0,1,0,0,0,1,0,0,0,0],[0,1,0,1,0,0,0,0,0,0,0,0,1],[1,0,0,0,0,0,0,1,1,0,0,0,0],[0,0,0,2,0,0,0,1,0,0,0,0,0],[0,0,1,0,0,0,2,0,0,0,0,0,0],[0,0,1,1,0,0,0,0,0,0,0,1,0],[0,0,0,1,1,1,0,0,0,0,0,0,0],[0,0,1,1,0,0,0,0,0,0,1,0,0],[1,0,0,0,0,0,1,0,0,1,0,0,0],[1,0,0,0,0,1,0,0,0,0,0,1,0],[0,1,0,0,0,1,0,1,0,0,0,0,0],[1,0,0,0,0,1,0,0,0,0,1,0,0],[1,0,0,0,1,0,0,0,0,0,0,0,1],[0,1,0,0,1,0,0,0,1,0,0,0,0],[0,0,1,0,1,0,0,1,0,0,0,0,0],[0,1,0,0,0,0,2,0,0,0,0,0,0],[0,1,0,1,0,0,0,0,0,0,0,1,0],[1,0,0,0,0,0,0,2,0,0,0,0,0],[0,0,1,0,0,1,1,0,0,0,0,0,0],[0,0,1,1,0,0,0,0,0,1,0,0,0],[0,1,0,1,0,0,0,0,0,0,1,0,0],[1,0,0,0,0,0,1,0,1,0,0,0,0],[1,0,0,0,0,1,0,0,0,1,0,0,0],[0,0,0,1,2,0,0,0,0,0,0,0,0],[0,0,0,2,0,0,1,0,0,0,0,0,0],[1,0,0,0,1,0,0,0,0,0,0,1,0],[0,1,0,0,1,0,0,1,0,0,0,0,0],[1,0,0,0,1,0,0,0,0,0,1,0,0],[0,1,0,0,0,1,1,0,0,0,0,0,0],[0,1,0,1,0,0,0,0,0,1,0,0,0],[0,0,1,0,0,2,0,0,0,0,0,0,0],[0,0,1,1,0,0,0,0,1,0,0,0,0],[0,0,2,0,0,0,0,0,0,0,0,0,1],[0,0,1,0,1,0,1,0,0,0,0,0,0],[1,0,0,0,0,0,1,1,0,0,0,0,0],[1,0,0,0,0,1,0,0,1,0,0,0,0],[0,0,0,2,0,1,0,0,0,0,0,0,0],[1,0,0,0,1,0,0,0,0,1,0,0,0],[1,0,0,1,0,0,0,0,0,0,0,0,1],[0,1,0,0,0,2,0,0,0,0,0,0,0],[0,1,0,1,0,0,0,0,1,0,0,0,0],[0,1,1,0,0,0,0,0,0,0,0,0,1],[0,0,1,1,0,0,0,1,0,0,0,0,0],[0,0,2,0,0,0,0,0,0,0,0,1,0],[0,1,0,0,1,0,1,0,0,0,0,0,0],[0,0,1,0,1,1,0,0,0,0,0,0,0],[0,0,2,0,0,0,0,0,0,0,1,0,0],[1,0,0,0,0,1,0,1,0,0,0,0,0],[1,0,0,0,1,0,0,0,1,0,0,0,0],[0,0,0,2,1,0,0,0,0,0,0,0,0],[0,2,0,0,0,0,0,0,0,0,0,0,1],[1,0,0,0,0,0,2,0,0,0,0,0,0],[1,0,0,1,0,0,0,0,0,0,0,1,0],[0,1,0,1,0,0,0,1,0,0,0,0,0],[0,1,1,0,0,0,0,0,0,0,0,1,0],[1,0,0,1,0,0,0,0,0,0,1,0,0],[0,0,2,0,0,0,0,0,0,1,0,0,0],[0,1,0,0,1,1,0,0,0,0,0,0,0],[0,1,1,0,0,0,0,0,0,0,1,0,0],[0,0,1,0,2,0,0,0,0,0,0,0,0],[0,0,1,1,0,0,1,0,0,0,0,0,0],[1,0,0,0,1,0,0,1,0,0,0,0,0],[0,2,0,0,0,0,0,0,0,0,0,1,0],[1,0,0,0,0,1,1,0,0,0,0,0,0],[1,0,0,1,0,0,0,0,0,1,0,0,0],[0,1,1,0,0,0,0,0,0,1,0,0,0],[0,2,0,0,0,0,0,0,0,0,1,0,0],[0,0,2,0,0,0,0,0,1,0,0,0,0],[0,1,0,0,2,0,0,0,0,0,0,0,0],[0,1,0,1,0,0,1,0,0,0,0,0,0],[0,0,1,1,0,1,0,0,0,0,0,0,0],[0,2,0,0,0,0,0,0,0,1,0,0,0],[1,0,0,0,0,2,0,0,0,0,0,0,0],[1,0,0,1,0,0,0,0,1,0,0,0,0],[1,0,1,0,0,0,0,0,0,0,0,0,1],[0,0,0,3,0,0,0,0,0,0,0,0,0],[0,1,1,0,0,0,0,0,1,0,0,0,0],[1,0,0,0,1,0,1,0,0,0,0,0,0],[0,0,2,0,0,0,0,1,0,0,0,0,0],[0,1,0,1,0,1,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0,0,0,0,1],[0,0,1,1,1,0,0,0,0,0,0,0,0],[0,2,0,0,0,0,0,0,1,0,0,0,0],[1,0,0,1,0,0,0,1,0,0,0,0,0],[1,0,1,0,0,0,0,0,0,0,0,1,0],[0,1,1,0,0,0,0,1,0,0,0,0,0],[1,0,0,0,1,1,0,0,0,0,0,0,0],[1,0,1,0,0,0,0,0,0,0,1,0,0],[0,0,2,0,0,0,1,0,0,0,0,0,0],[0,1,0,1,1,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0,0,0,1,0],[0,2,0,0,0,0,0,1,0,0,0,0,0],[1,0,1,0,0,0,0,0,0,1,0,0,0],[1,1,0,0,0,0,0,0,0,0,1,0,0],[1,0,0,0,2,0,0,0,0,0,0,0,0],[1,0,0,1,0,0,1,0,0,0,0,0,0],[0,1,1,0,0,0,1,0,0,0,0,0,0],[0,0,2,0,0,1,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0,1,0,0,0],[1,0,1,0,0,0,0,0,1,0,0,0,0],[0,0,1,2,0,0,0,0,0,0,0,0,0],[0,2,0,0,0,0,1,0,0,0,0,0,0],[1,0,0,1,0,1,0,0,0,0,0,0,0],[0,1,1,0,0,1,0,0,0,0,0,0,0],[2,0,0,0,0,0,0,0,0,0,0,0,1],[1,1,0,0,0,0,0,0,1,0,0,0,0],[0,0,2,0,1,0,0,0,0,0,0,0,0],[0,1,0,2,0,0,0,0,0,0,0,0,0],[1,0,1,0,0,0,0,1,0,0,0,0,0],[0,2,0,0,0,1,0,0,0,0,0,0,0],[1,0,0,1,1,0,0,0,0,0,0,0,0],[2,0,0,0,0,0,0,0,0,0,0,1,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,1,0,0,0,0,0],[2,0,0,0,0,0,0,0,0,0,1,0,0],[1,0,1,0,0,0,1,0,0,0,0,0,0],[0,2,0,0,1,0,0,0,0,0,0,0,0],[2,0,0,0,0,0,0,0,0,1,0,0,0],[0,0,2,1,0,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,1,0,0,0,0,0,0],[1,0,1,0,0,1,0,0,0,0,0,0,0],[2,0,0,0,0,0,0,0,1,0,0,0,0],[1,0,0,2,0,0,0,0,0,0,0,0,0],[0,1,1,1,0,0,0,0,0,0,0,0,0],[1,1,0,0,0,1,0,0,0,0,0,0,0],[1,0,1,0,1,0,0,0,0,0,0,0,0],[2,0,0,0,0,0,0,1,0,0,0,0,0],[0,2,0,1,0,0,0,0,0,0,0,0,0],[1,1,0,0,1,0,0,0,0,0,0,0,0],[2,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,3,0,0,0,0,0,0,0,0,0,0],[1,0,1,1,0,0,0,0,0,0,0,0,0],[0,1,2,0,0,0,0,0,0,0,0,0,0],[2,0,0,0,0,1,0,0,0,0,0,0,0],[1,1,0,1,0,0,0,0,0,0,0,0,0],[0,2,1,0,0,0,0,0,0,0,0,0,0],[2,0,0,0,1,0,0,0,0,0,0,0,0],[0,3,0,0,0,0,0,0,0,0,0,0,0],[1,0,2,0,0,0,0,0,0,0,0,0,0],[2,0,0,1,0,0,0,0,0,0,0,0,0],[1,1,1,0,0,0,0,0,0,0,0,0,0],[1,2,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,2],[0,0,0,0,0,0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,0,0,0,1,0,1],[2,0,1,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,2,0],[0,0,0,0,0,0,0,0,0,1,0,0,1],[0,0,0,0,0,0,0,0,0,0,1,1,0],[0,0,0,0,0,0,0,0,0,0,2,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,0,1,0],[0,0,0,0,0,0,0,0,1,0,0,0,1],[0,0,0,0,0,0,0,0,0,1,1,0,0],[0,0,0,0,0,0,0,0,0,2,0,0,0],[0,0,0,0,0,0,0,0,1,0,0,1,0],[0,0,0,0,0,0,0,1,0,0,0,0,1],[0,0,0,0,0,0,0,0,1,0,1,0,0],[0,0,0,0,0,0,0,0,1,1,0,0,0],[0,0,0,0,0,0,0,1,0,0,0,1,0],[0,0,0,0,0,0,0,1,0,0,1,0,0],[3,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,2,0,0,0,0],[0,0,0,0,0,0,0,1,0,1,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,1,0],[0,0,0,0,0,1,0,0,0,0,0,0,1],[0,0,0,0,0,0,1,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0],[0,0,0,0,0,0,1,0,0,1,0,0,0],[0,0,0,0,0,1,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,2,0,0,0,0,0],[0,0,0,0,0,0,1,0,1,0,0,0,0],[0,0,0,0,0,1,0,0,0,1,0,0,0],[0,0,0,0,1,0,0,0,0,0,0,1,0],[0,0,0,0,1,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,1,1,0,0,0,0,0],[0,0,0,0,0,1,0,0,1,0,0,0,0],[0,0,0,0,1,0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,0,1],[0,0,0,0,0,1,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,2,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,1,0],[0,0,0,1,0,0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,1,0,0,0,0,0],[0,0,0,0,0,1,1,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,2,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0,1],[0,0,0,0,1,0,1,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,0,0,1],[0,0,0,1,0,0,0,1,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,1,0],[0,0,0,0,1,1,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,1,0,0],[0,1,0,0,0,0,0,0,0,0,0,1,0],[0,0,1,0,0,0,0,0,0,1,0,0,0],[0,1,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,2,0,0,0,0,0,0,0,0],[0,0,0,1,0,0,1,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,1,0,0,0],[0,0,1,0,0,0,0,0,1,0,0,0,0],[0,0,0,1,0,1,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,1],[0,1,0,0,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,1,1,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0,0,1,0],[0,1,0,0,0,0,0,1,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,1,0,0,0,1,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,1,0,0,0],[0,1,0,0,0,0,1,0,0,0,0,0,0],[0,0,1,0,0,1,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,1,0,0,0,0],[0,0,0,2,0,0,0,0,0,0,0,0,0],[0,1,0,0,0,1,0,0,0,0,0,0,0],[0,0,1,0,1,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,1,1,0,0,0,0,0,0,0,0,0],[1,0,0,0,0,1,0,0,0,0,0,0,0],[0,1,0,1,0,0,0,0,0,0,0,0,0],[1,0,0,0,1,0,0,0,0,0,0,0,0],[0,0,2,0,0,0,0,0,0,0,0,0,0],[1,0,0,1,0,0,0,0,0,0,0,0,0],[0,1,1,0,0,0,0,0,0,0,0,0,0],[0,2,0,0,0,0,0,0,0,0,0,0,0],[1,0,1,0,0,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0,0,0,0,0],[2,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,0]]).

% The wastes
wastes([0,0,10,10,10,10,20,20,20,20,20,20,20,30,30,30,30,30,40,40,50,50,60,60,60,60,70,70,70,70,80,80,80,80,80,80,80,90,100,100,110,110,110,120,120,120,120,130,130,130,140,140,140,140,150,150,150,160,160,170,170,170,180,180,180,190,190,190,190,200,200,200,210,220,220,220,220,230,230,230,240,240,250,250,250,260,260,270,270,280,280,280,290,290,290,300,300,310,320,320,320,330,330,330,340,340,340,350,360,360,360,360,370,370,370,380,380,380,400,400,400,410,410,410,420,420,430,440,440,450,460,460,460,460,470,470,470,480,490,500,510,510,510,510,520,520,520,550,550,550,560,560,560,580,580,590,600,600,610,620,630,630,640,640,650,660,660,660,680,690,690,700,700,700,730,740,740,770,770,780,790,800,810,820,840,840,850,880,910,920,950,960,960,990,1000,1020,1040,1100,1130,1140,1180,1200,1250,1260,1280,1300,1300,1310,1320,1320,1350,1350,1360,1400,1400,1400,1410,1450,1450,1460,1460,1470,1500,1500,1520,1520,1530,1550,1570,1570,1580,1580,1600,1620,1620,1630,1640,1670,1670,1680,1690,1720,1730,1740,1740,1750,1780,1790,1790,1840,1840,1840,1850,1880,1890,1890,1900,1900,1930,1940,1940,1960,1960,1980,1990,2010,2020,2030,2040,2070,2070,2080,2080,2110,2120,2150,2160,2170,2180,2200,2220,2220,2260,2290,2330,2340,2370,2400,2480,2510,2520,2560,2660,2700,2840,3400,3450,3460,3500,3550,3600,3670,3720,3780,3890,4040,4080,4220]).