Студент Арсений любит планировать свои действия ровно на n дней вперед. Он каждый день ходит в столовую обедать, и поэтому он уже определился, что он будет заказывать в каждый из этих n дней. Цены в столовой не меняются, поэтому в i-й из этих дней Арсений пообедает ровно на ci рублей.
В ходу монеты номиналом 1 рубль и купюры номиналом 100 рублей. У Арсения сейчас имеется m монет и достаточно много купюр (вы можете считать, что бесконечно много). Арсений любит современные технологии, поэтому везде, кроме столовой, он расплачивается карточкой, а в столовой карточки не принимают, и ему приходится расплачиваться наличными.
Кассир всегда просит студента расплатиться без сдачи. К сожалению, это не всегда возможно, но Арсений старается минимизировать недовольство кассира. Недовольство кассира в каждый из дней определяется суммарным количеством монет и купюр в сдаче Арсению в этот день, а именно, если кассир сдал x купюр и монет в день i, то его недовольство в этот день равно x·wi. Кассир всегда выдает сдачу наименьшим возможным числом купюр и монет, у него достаточно монет и купюр для этого.
Арсений хочет расплачиваться так, чтобы минимизировать суммарное недовольство кассира за n дней. Помогите ему определить, как ему стоит расплачиваться в каждый из n дней!
Заметьте, что Арсению всегда хватит денег, чтобы расплатиться, так как у него бесконечно много купюр. Арсений может использовать монеты и купюры, полученные в сдаче, в любой из следующих дней.
Выходные данные
В первой строке выведите одно целое число — минимальное суммарное недовольство кассира, которого может достичь Арсений.
Далее выведите n строк. В i-й из этих строк выведите два числа — число купюр и число монет, которыми Арсений должен расплатиться в i-й день.
Естественно, в любой из дней сумма, которую даст Арсений, должна быть не меньше суммы, на которую он собирается пообедать. Также эта сумма не должна превышать 106 рублей: Арсений никогда не носит большие суммы с собой.
Если оптимальных ответов несколько, выведите любой.