В то время как в далёком космосе люди летают между планетами и исследуют новые миры, жители Земли всё так же каждый день просыпаются с утра, едут на работу, вечером возвращаются домой и пытаются хоть как-то отдохнуть. И среди них всё больше зреет недовольство и зависть по отношению к тем, кто может себе позволить свободно летать в космос.

Правительство Земли такая ситуация не устраивает. Его цель — сделать абсолютно всех людей счастливыми. Но поскольку всех сразу счастливыми сделать сложно, решили начать с уездного города Люкс, а потом, в случае успеха, перенести полученный опыт на более крупные города.

Особенностью Люкса является то, что он расположен в длинном подземном тоннеле, и поэтому в нём ходит всего одна электричка. Этой электричкой ежедневно пользуется почти всё население города. Правительство приобрело машину по массовой промывке мозгов и установило её в электричке. Поскольку влияние машины на человека не до конца изучено, было решено ограничить количество перегонов между соседними станциями, на которых будет включаться машина. Уже собрана полная статистика по тому, сколько людей ежедневно проезжает между каждой парой станций. Осталось выбрать, на каких перегонах включать машину, чтобы осчастливить как можно больше людей.

В первой строке записаны целые числа n и k — общее количество остановок электрички и количество перегонов, на которых было решено включать машину счастья (2 ≤ n ≤ 500; 1 ≤ k ≤ n − 1). В i-й из следующих n − 1 строк записаны n − i целых чисел, j-е из которых обозначает количество пассажиров, входящих на станции i и выходящих на станции i + j. Эти числа неотрицательны и не превосходят 100. Следует считать, что каждый пассажир пользуется электричкой только один раз в день.

В первой строке выведите общее количество осчастливленных пассажиров. Во второй строке выведите k целых чисел в порядке возрастания — номера перегонов, на которых нужно включать машину счастья. Перегон между станциями i и i + 1 имеет номер i. Если задача имеет несколько решений, выведите любое из них.