Skyland
n
Десь у небі королівство KM за допомогою своєї високорозвиненої технології побудувало плаваючі острови. Острови пронумеровані від 1 до n.
Король країни, Kita_masa, може вибрати будь-яке невід'ємне дійсне число як висоту для кожного острова, за умови, що сума висот є більшою або дорівнює H. Для підняття острова на висоту h_i, це коштує b_i h_i. Крім того, це коштує c_{i,j} |h_i−h_j| для кожної пари островів i і j, оскільки між цими островами є зв'язок.
Нещодавно ціни на енергію зростають, тому король, Kita_masa, хоче мінімізувати суму витрат. Він наказав вам, придворному програмісту, написати програму, яка знаходить висоти плаваючих островів, що мінімізують вартість.
Вхідні дані
Вхід містить декілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа (n та H), розділені одним пробілом. Наступний рядок містить цілі числа b_1, b_2, ..., b_n. Кожен з наступних n рядків містить n цілих чисел c_{i,j}. Ви можете припустити, що 1 ≤ n ≤ 100 та 0 ≤ H ≤ 1000. Значення b_i та c_{i,j} задовольняють 0 ≤ b_i ≤ 1000 та 0 ≤ c_{i,j} ≤ 1000, причому c_{i,i} = 0 та c_{i,j} = c_{j,i}.
Останній тестовий випадок супроводжується рядком, що містить два нулі.
Вихідні дані
Для кожного тестового випадку виведіть його номер. Потім виведіть рядок, що містить список висот островів, розділених пробілом, які мінімізують суму витрат. Якщо є декілька можливих рішень, виведіть будь-яке з них. Ваша відповідь буде прийнята, якщо висота кожного острова є невід'ємною, сума висот є більшою за H, а вартість, обчислена з вашої відповіді, має абсолютну або відносну похибку менше 10^{-9} від оптимального рішення.
Дотримуйтесь формату зразка виводу.