program Ferda;
const
  MaxN = 1000;
  MaxK = 10;
  Null = -1;
var
  O: array[0..MaxN, 0..MaxN * MaxK] of Integer;
  T: array[0..MaxN, 0..MaxN * MaxK] of Boolean;
  H, D: array[0..MaxN] of Integer;
  K, N, R: Integer;

  I, S: Integer;
begin
  Readln(N, K);
  for I:= 1 to N do 
  Readln(H[I], D[I]);

  for I:= 0 to N do
  for S:= 0 to N * K do
  O[I, S]:= Null;

  O[0, 0]:= 0;
  for I:= 0 to N - 1 do
  for S:= 0 to K * N do
  if O[I, S] <> Null then
  begin
    if (O[I + 1, S + H[I + 1]] = Null) or (O[I, S] < O[I + 1, S + H[I + 1]]) then 
    begin
      O[I + 1, S + H[I + 1]]:= O[I, S];
      T[I + 1, S + H[I + 1]]:= False;
    end;
    if (O[I + 1, S + D[I + 1]] = Null) or (O[I, S] + 1 < O[I + 1, S + D[I + 1]]) then
    begin
      O[I + 1, S + D[I + 1]]:= O[I, S] + 1;
      T[I + 1, S + D[I + 1]]:= True;
    end;
  end;

  R:= 0;
  for I:= 1 to N do
  R:= R + H[I] + D[I];

  for I:= R div 2 downto 0 do
  if (O[N, I] <> Null) or (O[N, R - I] <> Null) then
  begin
    if (O[N, R - I] = Null) or (O[N, I] <= O[N, R - I]) then
      R:= I else R:= R - I;
  end;

  for I:= N downto 1 do
  if T[N, R] then 
  begin
    Writeln(I);
    R:= R - D[I];
  end else
    R:= R - H[I];
end;