Акции
(Время: 1 сек. Память: 16 Мб Сложность: 28%)
Корпорация «Buy & Sell» для привлечения денежных средств в свой бизнес выпустила акции, цена которых ежедневно изменялась в течении N дней.
Василий Петрович, имея в наличии сумму в размере S рублей, решил на этом заработать и в один из дней купил акции на всю сумму (в результате покупки у него могла остаться сумма, меньшая стоимости одной акции), а затем в этот или в один из последующих дней, он продал все акции.
Требуется вычислить минимальную и максимальную возможную сумму, которая могла бы быть у Василия Петровича после продажи акций.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральные числа N и S – количество дней и стартовая сумма. Вторая строка содержит N натуральных чисел Ai – цены одной акции с 1-го по N-й день. Все числа во входных данных не превышают 105.
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа, разделенных пробелом: искомую минимальную и максимальную возможную сумму.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 100
17 14 11 20 15 | 70 181 |
2 | 5 10
1 2 3 4 5 | 10 50 |
Пояснения к примерам
В первом примере наименее прибыльно купить 5 акций в первый день (15+5*17=100) и продать их в третий день (15+5*11=70). Наиболее выгодно акции покупать в третий день (1+9*11=100) и продать их в четвертый день (1+9*20=181).
Во втором примере наихудшим вариантом будет служить тот, когда покупка и продажа протекают в один и тот же день. Наилучший исход – это покупка в первый день, а продажа – в последний.
Система оценки
Решения, работающие только для N = 5, будут оцениваться в 20 баллов.
Решения, работающие только для N ≤ 1000, будут оцениваться в 60 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|