{
  Idëja:

  Rekursiðkai skaièiuojame maþiausià reikiamø rezistoriø skaièiø
  trupmenoms a/b - 1/i, kai i kinta nuo (b - 1) div a + 1 iki
  jau rasto minimalaus rezistoriø skaièiaus minus tiek, kiek
  buvo panaudota kitoms grupelëms sudaryti. Jeigu galime,
  apskaièiuotus tarpinius rezultatus saugome masyve ið
  kurio tas reikðmes galime paimti, jei tà paèià trupmenà
  tenka sudaryti dar kartà.
  Kadangi tarpines reikðmes skaièiuojame imdami tik tam tikrà
  ribotà skaièiø rezistoriø, minimalaus varianto galime ir
  nerasti (taèiau tuo momentu rezultatas mus vis tiek tenkina).
  Jei maksimalus galimas rezistoriø skaièius padidëja,
  anksèiau paskaièiuotos reikðmës negalime imti, todël tenka
  jà perskaièiuoti su "didesniu tikslumu".

}

program Schemos;

const
  MAX_MAS = 1400;
  MAX_ATS = 1000;

type
  TRac = record    { Racionalieji skaièiai }
    s, v: Longint; { Skaitiklis, Vardiklis }
  end;

  TDinMas = array[1..MAX_MAS, 1..MAX_MAS] of record
    Min, Max: Longint; { Minimalus varþø sk., Maksimalus "tikslumas" }
  end;

var
  R: TRac;      { Radiniai duomenys: R/r }
  Ats: Longint; { Atsakymas }
  D: TDinMas;   { Dinaminio skaièiavimo masyvas }

{ --- Ávedimo/Iðvedimo procedûros --- }
procedure ivesti_duomenis;
var
  f: Text;
begin
  Assign(f, 'SCHEM.DAT');
  Reset(f);
    ReadLn(f, R.v, R.s); { Perskaitom R/r }
  Close(f);
end;

procedure isvesti_duomenis;
var
  f: Text;
begin
  Assign(f, 'SCHEM.REZ');
  Rewrite(f);
    if Ats > MAX_ATS then
      WriteLn(f, 'NEGAMINTI')
    else
      WriteLn(f, Ats);
  Close(f);
end;

{ --- Procedûros darbui su racionaliaisiais skaièiais --- }

{ Patogus bûdas uþpildyti TRac struktûrà }
function Rac(s, v: Longint): TRac;
begin
  Rac.s := s;
  Rac.v := v;
end;

{ Didþiausias Bendras Daliklis, Euklido alg. }
function dbd(a, b: Longint): Longint;
var
  c: Longint;
begin
  if (a <= 0) or (b <= 0) then
    dbd := 1
  else
  begin
    if a < b then begin c := a; a := b; b := c; end;
    { a >= b >= 0 }
    while b <> 0 do
    begin
      c := a mod b;
      a := b; b := c;
    end;
    dbd := a;
  end;
end;

{ Normalizuoti (suprastinti) A }
procedure Norm(var A: TRac);
var
  d: Longint;
begin
  if A.s >= 0 then
    d := dbd(A.s, A.v)
  else
    d := dbd(-A.s, A.v);
  if d > 1 then
  begin
    A.s := A.s div d;
    A.v := A.v div d;
  end;
end;

{ Gràþina A - B }
function Skirt(A, B: TRac): TRac;
var
  C: TRac;
begin
  C.s := A.s * B.v - B.s * A.v;
  C.v := A.v * B.v;
  Norm(C);
  Skirt := C;
end;

{ --- Duomenø analizës procedûros --- }

{ Gràþina minimalø sk. rezistoriø schemai X (a/b),
  maksimalus galimas rezistoriø sk. MaxN }
function MinSk (X: TRac; MaxN: Longint): Longint;
var
  MinN, MinI, I, S: Longint;
  U: TRac;
begin
  MinN := MaxN; MinI := 1;
  { Tikriname, ar nëra akivaizdaus atsakymo }
  if X.s = 1 then        { 1/a }
    MinSk := X.v
  else
  if X.v = 1 then        { a/1 }
    MinSk := X.s
  else
  begin
    { Tikriname, ar nesame atsakymo apskaièiavæ }
    if (X.s > MAX_MAS) or (X.v > MAX_MAS) then
    begin
      MinSk := MAX_ATS + 1;            { Netelpame á masyvà }
      Exit;
    end;
    if (D[X.s, X.v].Min <> 0) and (D[X.s, X.v].Max >= MaxN) then
    begin
      MinSk := D[X.s, X.v].Min; { Naudojame reikðmæ, apskaièiuotà anksèiau }
      Exit;
    end;
    { Turime patikrinti grupeles nuo 1/MinI iki 1/MaxN (pakaks ir 1/MinN) }
    I := MinI;
    MinI := (X.v - 1) div X.s + 1;
    if MinI > I then
      I := MinI;

    while I < MinN do
    begin
      { Skeliam á 1/I + a/b }
      U := Skirt(X, Rac(1, I));
      S := I + MinSk(U, MinN - I); { Daugiau rezist. nei MinN - I nereikia }
      if S < MinN then
        MinN := S;
      Inc(I);
    end;
    { MinN - maþiausias rezist. skaièius, norint gauti X }
      D[X.s, X.v].Min := MinN;
      D[X.s, X.v].Max := MaxN;
    MinSk := MinN;
  end;
end;

procedure ivertinti_situacija;
begin
  Norm(R); { Suprastiname R/r }
  Ats := R.s * R.v; { Pradinis maksimumas (R grupiø po r varþø) }
  if Ats > MAX_ATS then
    Ats := MAX_ATS + 1; { Norësim þinoti, kada 'NEGAMINTI' }
  Ats := MinSk(R, Ats);
end;

begin
  ivesti_duomenis;
  ivertinti_situacija;
  isvesti_duomenis;
end.

