{*************************************************************************
 *                                                                       *
 *                    XI Olimpiada Informatyczna                         *
 *                                                                       *
 *   Rozwiązanie zadania: Przeprawa                                      *
 *   Plik:                prz.pas                                        *
 *   Autor:               Paweł Wolff                                    *
 *   Data:                2003.10.29                                     * 
 *************************************************************************}

program Przeprawa;

const
  MAX_N = 16;
  MAX_T = 50;
  DWA_DO_MAX_N = 65536;


type
  TBajtolaz =
    record
      t: integer;
      w: integer;
    end;
    
  TTabBajtolazow = array [1..MAX_N] of TBajtolaz;
  
  TTabZnacznikow = array [1..MAX_N] of boolean;
  

var
  n: integer; { liczba Bajtołazów }
  b: TTabBajtolazow; { opis Bajtołazów }
  
  w: integer; { maksymalne dopuszczalne obciążenie mostu }
  
  obliczonyCzas: array [0..DWA_DO_MAX_N - 1] of integer;
    { tu zapamiętujemy obliczone już czasy przeprawy podzbiorów zbioru
      wszystkich Bajtołazów }
  

procedure WczytajDane(var z: TTabZnacznikow);
var
  i: integer;
begin
  Readln(w, n);
  for i := 1 to n do begin
    with b[i] do
      Readln(t, w);
    z[i] := true;
  end;
end;


function NajwolniejszyBajtolaz(var z: TTabZnacznikow): integer;
{ zwraca indeks najwolniejszego nieprzeprawionego Bajtołaza; jeżeli takiego
  nie ma, to zwraca 0 }
var
  i: integer;
  maxT: integer;  
begin
  maxT := 0;
  NajwolniejszyBajtolaz := 0;
  
  for i := 1 to n do
    if z[i] and (b[i].t > maxT) then begin
      NajwolniejszyBajtolaz := i;
      maxT := b[i].t;
    end;
end;


function Indeks(var z: TTabZnacznikow): longint;
{ przekształca tablicę znaczników z na indeks w tablicy obliczonyCzas }
var
  ind: longint;
  i: integer;

begin
  ind := 0;
  for i := 1 to n do begin
    ind := 2 * ind;
    if z[i] then
      Inc(ind);
  end;

  Indeks := ind;
end;

function ZapamietanyWynik(var z: TTabZnacznikow): integer;
{ zwraca zapamiętany czas przeprawy podzbioru Bajtołazów określony w tablicy z }
begin
  ZapamietanyWynik := obliczonyCzas[Indeks(z)];
end;

procedure ZapamietajWynik(var z: TTabZnacznikow; wynik: integer);
{ zapisuje (w tablicy obliczonyCzas) minimalny czas (określony w zmiennej
  wynik) przeprawy podzbioru Bajtołazów określonego w tablicy z }
begin
  obliczonyCzas[Indeks(z)] := wynik;
end;


function ObliczWynik(var z: TTabZnacznikow): integer;
{ zwraca minimalny czas przeprawy podzbioru Bajtołazów określonego w tablicy z }

  procedure WydzielGrupe(var z: TTabZnacznikow; var wynik, wagaGrupy: integer;
                         ostatniWGrupie: integer);
  { powiększa grupę Bajtołazów (zainicjowaną w funkcji ObliczWynik)
    o Bajtołazów z podzbioru określonego przez tablicę z i o indeksach
    większych niż ostatniWGrupie; robi to na wszystkie takie sposoby,
    które prowadzą do tego, że wynikowa grupa (o inicjalnej sumarycznej wadze
    wagaGrupy) jest możliwie jak największa (ściśle rzecz biorąc - maksymalna
    w sensie inkluzji) oraz że jej waga nie przekracza w (dopuszczalnego
    obciążenia mostu);
    dla wszystkich tak powiększonych grupy oblicza minimalny czas takiej
    przeprawy Bajtołazów (z podzbioru określonego przez tablicę z), że
    najpierw przeprawiani są Bajtołazi z grupy, a następnie pozostali;
    przez parametr wynik przekazuje najkrótszy czas przeprawy wykonanej
    wg powyższego schematu }
  var
    i, wynikPom: integer;
    
  begin
    i := ostatniWGrupie + 1;
    while i <= n do begin

      { szukamy następnego Bajtołaza w podzbiorze określonym przez z }
      while (i <= n) and not z[i] do
        Inc(i);
      
      if i <= n then begin { jeśli jeszcze kogoś (i-tego Bajtołaza) można dodać
                             do grupy... }
        if wagaGrupy + b[i].w <= w then begin { i na dodatek powiększona
	                     o niego grupa nie przeciąża mostu, to... }
          { dodajemy i-tego Bajtołaza do przeprawianej grupy }
          z[i] := false;
          Inc(wagaGrupy, b[i].w);
	  
	  WydzielGrupe(z, wynik, wagaGrupy, i);

          { usuwamy i-tego Bajtołaza z przeprawianej grupy }
	  z[i] := true;
          Dec(wagaGrupy, b[i].w);
        end;
        Inc(i); { rozpatrujemy następnego Bajtołaza }
      end
    end;

    { sprawdzamy, czy grupa jest maksymalna... }
    i := 1;
    while (i <= n) and not (z[i] and (wagaGrupy + b[i].w <= w)) do
      Inc(i);

    if i > n then begin
      { grupa jest maksymalna... }
      wynikPom := ObliczWynik(z); { więc liczymy minimalny czas przeprawy
                                    reszty Bajtołazów }
      ZapamietajWynik(z, wynikPom);
      if wynikPom < wynik then
        wynik := wynikPom;
    end;
  end;

var
  i, wynik, wagaGrupy: integer;

begin
  wynik := ZapamietanyWynik(z); { może już dla takiego podzbioru Bajtołazów
                                  mamy policzony wynik? }
  if wynik <> 0 then { tak, już go policzyliśmy }
    ObliczWynik := wynik
  else begin
    { nie, teraz będziemy go liczyć }
    i := NajwolniejszyBajtolaz(z);
    if i = 0 then begin { wszyscy są przeprawieni (z definiuje zbiór pusty) }
      ZapamietajWynik(z, 0);
      ObliczWynik := 0
    end
    else begin
      wynik := MAX_N * MAX_T; { dłużej już przeprawa trwać nie może }

      wagaGrupy := b[i].w;
      z[i] := false;
      { inicjalnie grupa składa się z najwolniejszego Bajtołaza, który
        nie został jeszcze przeprawiony }
      WydzielGrupe(z, wynik, wagaGrupy, 0);
      z[i] := true;

      ObliczWynik := b[i].t + wynik;
    end;
  end;
end;



var
  doPrzeprawienia: TTabZnacznikow; { określa, który z Bajtołazów jest jeszcze
                                     nieprzeprawiony }
  i: longint;
  dwaDoN: longint;

begin
  WczytajDane(doPrzeprawienia);

  { zerujemy tablice obliczonyWynik }
  dwaDoN := 1;
  for i := 1 to n do
    dwaDoN := 2 * dwaDoN;
  for i := 0 to dwaDoN - 1 do
    obliczonyCzas[i] := 0;

  { obliczamy i zapisujemy wynik }
  Writeln(ObliczWynik(doPrzeprawienia));
end.
