← К соревнованиям

Sort Me Round

Торговый автомат

Сложность: 44%

На станции метро "Молодецкая" стоит вендинговый автомат, в котором можно купить только один товар – баночку немецкой газировки. Она стоит kk сорткоинов. Газировка так хороша, что за ней уже выстроилась очередь из nn покупателей, каждый из которых хочет купить как можно больше баночек. Автомат принимает только монетки номиналом в 1, 2, 5 и 10 сорткоинов.

К сожалению, разработку алгоритма приёма монет доверили крайне неопытному разработчику. Он реализовал его так: изначально счетчик сорткоинов равен нулю, а когда покупатель вбрасывает монету в автомат, алгоритм проверяет, достигла ли сумма номиналов вброшенных монет kk, и если да – то обнуляет счётчик и выдаёт банку. Сдача не возвращается покупателю.

Для каждого человека в очереди узнайте, какое максимально возможное число баночек у него получится купить. Покупатели не могут помогать друг другу, их следует рассматривать независимо.

Входные данные

Единственная строка, где через пробел записаны два числа nn и kk – количество покупателей в очереди и цена баночки немецкой газировки. (1n105; 1k5401 \le n \le 10^5;\ 1 \le k \le 540).

В каждой из следующих nn строк записано по 4 числа aa, bb, cc и dd – количество монет номиналом в 1, 2, 5 и 10 сорткоинов соответственно, которые есть с собой у ii-го покупателя. (0a,b,c,d300 \le a, b, c, d \le 30)

Выходные данные

Для каждого покупателя с новой строки выведите одно число – сколько баночек немецкой газировки он сможет купить.

Подзадачи

баллынеобх. подзадачиограничения
1

28

-

1a,b,c,d51 \le a, b, c, d \le 5

2

8

-

(a+2b+5c+10d)modk=0(a + 2b + 5c + 10d) \mod k = 0

3

28

-

n=1n = 1

4

36

1, 2, 3

Нет доп. ограничений

STDINSTDOUT
3 8
4 3 3 0
3 4 4 1
2 5 2 5
3
4
7