В настоящее время на бирже при торговле акциями активно применяются компьютерные системы, которые упрощают и автоматизируют процесс покупки и продажи акций. Некоторые из них даже позволяют вести торговлю вообще без участия человека.
Разумеется, основным критерием, по которому такие системы оцениваются, является прибыль, которую приносит торговля с их применением. Для того, чтобы ее повысить при построении этих систем применяются различные математические методы и модели, такие, как, например, квадратичное программирование, нейронные сети, генетические алгоритмы и т. д.
Основной трудностью при создании таких систем является то, что они должны некоторым образом учитывать изменение стоимости акций в будущем, а также его прогнозировать. Ваша задача несколько проще — курсы продажи и покупки акций за весь период из n дней уже известны, необходимо лишь разработать оптимальную стратегию продаж и покупок. При этом для простоты будем считать, что за эти n дней купить акции можно не более одного раза и продать акции можно также не более одного раза.
Кроме этого, будем считать, что продажа и покупка будет осуществляться только с акциями одного типа. На начало этого периода вы располагаете суммой в x рублей. Для каждого из дней известна цена ai (от ask — цена предложения), по которой можно купить одну акцию, и цена bi (от bid — цена спроса), по которой можно одну акцию продать. При этом в соответствии с действующими правилами торгов на бирже разрешается продавать и покупать только целое число акций (например, если у вас есть 5 рублей, а акция стоит 2 рубля, то вы можете купить не более двух акций).
Требуется написать программу, которая по имеющимся данным о стоимости акций в каждый из дней, найдет оптимальную стратегию покупки и продажи акций.
Входные данные
Первая строка входного файла содержит два целых числа n и x (1 ≤ n ≤ 100000, 1 ≤ x ≤ 106).
Вторая строка входного файла содержит n целых чисел a1, . . . , aт. Третья строка входного файла содержит n целых чисел b1, . . . , bт. Для каждого индекса i (1 ≤ i ≤ n) выполняются неравенства 1 ≤ bi ≤ ai ≤ 1000.
Выходные данные
В первой строке выходного файла выведите максимальную сумму, которой вы можете обладать по окончании рассматриваемого периода. Во второй строке выведите два числа — номер дня 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 |