Banzhaf Buzz-Off

Вхідні дані

Кожен тестовий випадок складається з двох рядків: перший рядок містить два цілі числа n та q, де n — це кількість різних значень ваги (1 ≤ n ≤ 60), а q — це квота. Другий рядок містить n пар додатних цілих чисел w_1 m_1 w_2 m_2 ... w_n m_n, де w_i — це значення ваги, а m_i — кількість членів ради з такою вагою. Загальна кількість голосів V = w_1m_1+w_2m_2+...+w_nm_n буде в межах 1 ≤ V ≤ 60. Квота задовольняє умову V/2 < q ≤ V, і w_i ≠ w_j для i ≠ j. Рядок "0 0" сигналізує про кінець вводу.

Вихідні дані

Для кожного тестового випадку виведіть один рядок у форматі:

Випадок n: b_1 b_2 ... b_n

де b_i — це Індекс Влади Бенцгафа для будь-якого члена з вагою w_i. Розділяйте Індекси Влади Бенцгафа пробілом.

Приклади