Кризисный бизнес

Петр Васильевич Колошин никогда не был пугливым человеком и всегда отличался спокойствием и прозорливостью, особенно в сфере мировых политических и экономических процессов. Однако, несмотря ни на что, Петр Васильевич очень недооценил последствия мирового финансового кризиса и, как следствие, был уволен пару недель назад с должности сетевого администратора одной большой и серьезной организации.

Несмотря ни на что, Петр Васильевич не отчаялся и решил начать свое дело. Тщательно проанализировав бизнес-климат в своем регионе, Петр Васильевич пришел к выводу, что наиболее целесообразным будет открыть новый таксопарк. Первое с чего решил начать новоиспеченный бизнесмен – это закупить автомобили. За все время работы Петр Васильевичу удалось накопить сумму S, которую он готов потратить на закупку машин.

В городе, в котором живет Петр Васильевич, есть только один автосалон. Известно, что в этом автосалоне выставлено на продажу N автомобилей, причем установлено, что стоимость i-го автомобиля равняется Ai. Вашей задачей является помочь еще неопытному бизнесмену Петр Васильевичу приобрести максимальное количество автомобилей, потратив сумму не более S.

Входные данные

В первой строке входного файла INPUT.TXT находится два целых положительных числа разделенные одиночным пробелом – это числа N (1 ≤ N ≤ 100) и S (1 ≤ S ≤ 109) соответственно.

Вторая строка содержит ровно N чисел Ai (1 ≤ Ai ≤ 109) , которые описывают стоимость соответствующих автомобилей. Все числа в строке разделены одиночными пробелами.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – максимальное количество автомобилей, которые сможет приобрести Петр Васильевич на сумму не более чем S.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	5 30 15 5 11 10 12	3
2	6 18 5 10 1 2 1 20	4

Решение

var m,k,t:longint;
a:array[1..100] of longint;
n,i,j:integer;
f,f1:text;
begin
   assign(f,'input.txt');
   reset(f);
   assign(f1,'output.txt');
   rewrite(f1);
   readln(f,n,m);
   k:=0;
   for i:=1 to n do
   read(f,a[i]);
   for i:=1 to n-1 do
     begin
       for j:=1 to n-i do
       if a[j]>a[j+1] then
        begin
            t:=a[j];
            a[j]:=a[j+1];
            a[j+1]:=t;
        end;
    end;
   i:=1;
   while m>0 do
    begin
        m:=m-a[i];
        i:=i+1;
        k:=k+1;
    end;

   if m<0 then k:=k-1;
   writeln(f1,k);
   close(f);
   close(f1);
end.