Задача №113535. Поищите без сдачи!
p1208
p113535
p113251
Студент Арсений любит планировать свои действия ровно на n дней вперед. Он каждый день ходит в столовую обедать, и поэтому он уже определился, что он будет заказывать в каждый из этих n дней. Цены в столовой не меняются, поэтому в i -й из этих дней Арсений пообедает ровно на c i рублей.
В ходу монеты номиналом 1 рубль и купюры номиналом 100 рублей. У Арсения сейчас имеется m монет и достаточно много купюр (вы можете считать, что бесконечно много). Арсений любит современные технологии, поэтому везде, кроме столовой, он расплачивается карточкой, а в столовой карточки не принимают, и ему приходится расплачиваться наличными.
Кассир всегда просит студента расплатиться без сдачи. К сожалению, это не всегда возможно, но Арсений старается минимизировать недовольство кассира. Недовольство кассира в каждый из дней определяется суммарным количеством монет и купюр в сдаче Арсению в этот день, а именно, если кассир сдал x купюр и монет в день i , то его недовольство в этот день равно x · w i . Кассир всегда выдает сдачу наименьшим возможным числом купюр и монет, у него достаточно монет и купюр для этого.
Арсений хочет расплачиваться так, чтобы минимизировать суммарное недовольство кассира за n дней. Помогите ему определить, как ему стоит расплачиваться в каждый из n дней!
Заметьте, что Арсению всегда хватит денег, чтобы расплатиться, так как у него бесконечно много купюр. Арсений может использовать монеты и купюры, полученные в сдаче, в любой из следующих дней.
В первой строке находятся два целых числа n и m ( 1 ≤ n ≤ 10 5 , 0 ≤ m ≤ 10 9 ) — число дней, на которые Арсений распланировал свои действия, и число имеющихся у него монет в данный момент.
Во второй строке находится последовательность целых чисел c 1 , c 2 , ..., c n ( 1 ≤ c i ≤ 10 5 ) — суммы, которые Арсений собирается потратить в каждый из дней.
В третьей строке находится последовательность целых чисел w 1 , w 2 , ..., w n ( 1 ≤ w i ≤ 10 5 ) — коэффициенты недовольства кассира в каждый из дней.
В первой строке выведите одно целое число — минимальное суммарное недовольство кассира, которого может достичь Арсений.
Далее выведите n строк. В i -й из этих строк выведите два числа — число купюр и число монет, которыми Арсений должен расплатиться в i -й день.
Естественно, в любой из дней сумма, которую даст Арсений, должна быть не меньше суммы, на которую он собирается пообедать. Также эта сумма не должна превышать 10 6 рублей: Арсений никогда не носит большие суммы с собой.
Если оптимальных ответов несколько, выведите любой.
В тестах суммарной стоимостью не менее 20 баллов будут выполняться ограничения 1 ≤ n ≤ 20 , 0 ≤ m ≤ 500 .
В тестах суммарной стоимостью не менее 40 баллов будут выполняться ограничения 1 ≤ n ≤ 500 , 0 ≤ m ≤ 500 .
В тестах суммарной стоимостью не менее 50 баллов будут выполняться ограничения 1 ≤ n ≤ 500 .
5 42 117 71 150 243 200 1 1 1 1 1
79 1 17 1 0 2 0 2 43 2 0
3 0 100 50 50 1 3 2
150 1 0 1 0 0 50
5 42 117 71 150 243 200 5 4 3 2 1
230 1 17 1 0 1 50 3 0 2 0