D. Танцевальный марафон
Задачу добавил: alef
Успешно сдано решений: 193
Почти каждый вечер на набережной устраивают танцевальный марафон, по итогам которого вручаются разные забавные призы. Кеша далёк от мысли, что он может получить приз за лучшее исполнение или приз зрительских симпатий. Однако он полагает, что за приз тому, кто дольше всех продержался на танцплощадке, он вполне мог бы побороться.
Кеша изучил плейлист перед началом очередного марафона и выяснил, что в нём запланировано n композиций длительностью t1, t2, ..., tn. Также Кеша для каждой композиции знает, сколько сил в единицу времени ему придётся тратить на исполнение соответствующего танца.
Чтобы побороться за желаемый приз, Кеша должен начать танцевать в момент, когда начнётся какой-либо танец. Прекратить танцевать он может в любой момент времени.
Для составления рейтинга участников организаторы подсчитывают количество танцев, которые участник исполнил полностью. В случае, если два или больше участников исполнили полностью одинаковое количество танцев, выше в рейтинге будет тот, кто большее количество целых единиц времени продержался в последнем танце, исполненном не до конца.
Кеша знает, что может потратить p единиц силы. Ваша задача — определить, с какого танца Кеша должен начать участвовать в соревновании.
В первой строке содержатся целые числа n и p (1 ≤ n ≤ 105, 1 ≤ p ≤ 109) — количество запланированных композиций и количество сил у Кеши в начальный момент времени.
Во второй строке содержится n целых чисел t1, t2, ..., tn (1 ≤ tj ≤ 106, j = 1, 2, ..., n) — длительности композиций.
В третьей строке содержится n целых чисел f1, f2, ..., fn (1 ≤ fj ≤ 106, j = 1, 2, ..., n), где fj — количество сил в единицу времени, которые будет тратить Кеша, исполняя танец под композицию #j.
Выведите номер танца, с которого Кеше следует начать участие в соревновании, максимально возможное количество танцев, которые Кеша сможет исполнить полностью, а также количество целых минут, которые Кеша продержится в последнем танце, который он исполнит не полностью.
Разделяйте числа пробелами или переводами строк.
Если существует несколько возможных ответов, выведите любой.
Подзадача 1 (до 20 баллов)
1 ≤ n ≤ 100, 1 ≤ tj ≤ 1000, 1 ≤ fj ≤ 1000
Баллы начисляются за каждый пройденный тест, по запросу сообщаются результаты проверки на каждом тесте.
Подзадача 2 (до 80 баллов)
Любые допустимые входные значения.
Баллы начисляются в случае прохождения всех тестов группы.
По запросу сообщается номер первого непройденного теста в группе.
4 10
7 2 2 5
1 2 3 1
2
2
0
10 100
3 5 2 7 5 3 8 4 6 6
2 7 3 4 5 6 1 8 7 2
3
5
1
Поясним первый из приведённых примеров.
Было запланировано 4 композиции. Соответственно, у Кеши есть 4 момента времени, в которые он может начать танцевать.
Если Кеша начнёт танцевать в момент начала первой композиции, то он потратит 7 единиц энергии (1 единица силы, умноженная на 7 единиц времени) на первый танец, а оставшихся трёх единиц энергии ему хватит, чтобы танцевать ещё одну полную минуту второго танца (на вторую минуту сил у Кеши уже не хватит). Таким образом, в этом случае у Кеши будет результат в виде одного полного танца и одной полной минуты в неоконченном танце.
Если Кеша начнёт танцевать в момент начала второй композиции, то ему хватит сил ровно на два полных танца: 4 единицы энергии он потратит на второй танец и 6 единиц — на третий. Поскольку неоконченного танца не будет совсем, то можно считать, что результатом Кеши будут два полных танца и 0 минут в неоконченном танце.
Если Кеша начнёт танцевать в момент начала третьей композиции, то после исполнения третьего танца у него останется 4 единицы энергии, которых хватит на 4 минуты в четвёртом танце. В этом случае результатом Кеши будет один полный танец и 4 минуты в неоконченном танце.
Наконец, если Кеша начнёт танцевать в момент начала четвёртой композиции, он потратит 5 единиц энергии на полный танец, и столько же у него останется — но расходовать их будет некуда: танцев больше не осталось. Результат (формальный) в этом случае — один полный танец и 0 минут в неоконченном танце.
Как можно видеть, наилучший результат достигается, если Кеша начнёт танцевать в момент начала второй композиции.