Задача №111121. Торговля акциями
В настоящее время на бирже при торговле акциями активно применяются компьютерные системы, которые упрощают и автоматизируют процесс покупки и продажи акций. Некоторые из них даже позволяют вести торговлю вообще без участия человека.
Разумеется, основным критерием, по которому такие системы оцениваются, является прибыль, которую приносит торговля с их применением. Для того, чтобы ее повысить при построении этих систем применяются различные математические методы и модели.
Основной трудностью при создании таких систем является то, что они должны некоторым образом учитывать изменение стоимости акций в будущем, а также его прогнозировать. Ваша задача несколько проще — курсы продажи и покупки акций за весь период из N дней уже известны, необходимо лишь разработать оптимальную стратегию продаж и покупок. При этом для простоты будем считать, что за эти N дней купить акции можно не более одного раза и продать акции можно также не более одного раза.
Кроме этого, будем считать, что продажа и покупка будет осуществляться только с акциями одного типа. На начало этого периода вы располагаете суммой в X рублей. Для каждого из дней известна цена ai (от ask — цена предложения), по которой можно купить одну акцию, и цена bi (от bid — цена спроса), по которой можно одну акцию продать. При этом в соответствии с действующими правилами торгов на бирже разрешается продавать и покупать только целое число акций (например, если у вас есть 5 рублей, а акция стоит 2 рубля, то вы можете купить не более двух акций). Требуется написать программу, которая по имеющимся данным о стоимости акций в каждый из дней, найдет оптимальную стратегию покупки и продажи акций.
Первая строка входного файла содержит два целых числа N и X (1 ≤ N ≤ 100 000, 1 ≤ X ≤ 106). Вторая строка входного файла содержит N целых чисел a1, ..., aN. Третья строка входного файла содержит N целых чисел b1, ..., bN (1 ≤ bi ≤ ai ≤ 1 000).
В первой строке выходного файла выведите максимальную сумму, которой вы можете обладать по окончании рассматриваемого периода. Во второй строке выведите два числа — номер дня d1, в который следует купить акции, и номер дня d2, в который эти акции следует продать (должно выполняться неравенство d2 > d1). При этом подразумевается, что покупается столько акций, сколько их можно купить на X рублей, а потом они все продаются. Если в найденной вами стратегии продавать и покупать акции не требуется, то выведите во второй строке « - 1 - 1». Если существует несколько вариантов оптимальной стратегии, то выведите любой из них.
5 1000
2 3 1 4 3
1 2 1 2 3
3000
3 5
5 1000
10 9 8 7 6
9 8 7 6 5
1000
-1 -1