Задача A. Сумма на часах ≡

Условие

На столе лежит n работающих пронумерованных от 1 до n часов.

В начальный момент времени часы под номером i показывают время t_i.

t_i представляет строку из пяти символов, в которой первые две цифры показывают значение часовой стрелки, затем следует разделитель ':' (ASCII 58), последние две цифры  — значение минутной стрелки.

Примеры: 12:30 — двенадцать часов тридцать минут, 01:05 — один час пять минут.

Необходимо узнать через какое время сумма цифр всех часов в первый раз будет равна S, или определить что данная сумма не будет набрана никогда.

Формат входного файла

Первая строка входного файла содержит два целых числа n и S  — количество часов и требуемая сумма соответственно.

Следующие n строк содержат t_i  — показания часов в начальный момент времени.

Формат выходного файла

Выходной файл должен содержать время в том же формате что и t_i, через которое сумма цифр в первый раз станет равна S.

В случае, если требуемая сумма не будет набрана никогда, выведите −1.

Ограничения

1 ≤ n ≤ 100

0 ≤ S ≤ 24 n

Примеры тестов

1 14
13:02

00:17

3 31
11:03
23:15
15:59

00:03

2 4
00:01
10:15

-1

2 30
20:20
00:15

03:34

Задача B. Загадочный ключ ≡

Условие

Однажды программист Вася отправился на поиски сокровищ в древнюю пирамиду. Добравшись до сокровищницы, он обнаружил перед собой квадратную дверь со стороной N. На двери был выточен странный орнамент, который Вася схематично изобразил у себя в дневнике символами "#" (ASCII 35) и "." (ASCII 46).

Днем ранее в другой пирамиде Вася нашел ключ. Теперь он хочет найти на двери отверстие для вставки ключа. Отверстие для вставки ключа выглядит как квадрат шириной K из символов "#" (ASCII 35), внутри которого располагаются только символы ".", а снаружи это отверстие может быть либо окружено границами двери, либо символами ".".

Однако, дверь оказалась довольно большой и Васе не хочется вручную искать на ней место для ключа, поэтому он просит вас написать программу, которая сделает это за него.

Формат входного файла

Первая строка входного файла содержит целые числa N и K.

Далее следует N строк по N символов  — описание орнамента двери.

Формат выходного файла

Выходной файл должен содержать два целых числа  — номера строки и столбца самого левого верхнего символа "#" отверстия для ключа (нумерация с единицы).

Если решений несколько, выведите любое из них. Если решения не существует, выведите −1.

Ограничения

1 ≤ N, K ≤ 100

Примеры тестов

2 1
..
.#

2 2

5 2
....#
.##.#
.####
....#
#.#.#

-1

7 4
#######
......#
.####..
.#..#..
.#..#..
.####..
.......

3 2

Задача C. Конфеты и самоконтроль ≡

Условие

Сегодня Петя и Вася купили себе K конфет. Петя предложил просто разделить их поровну и съесть, на что Вася ответил, что так не интересно и вместо этого предложил сыграть в игру.

Каждый по очереди берет конфеты из мешка. Первым ходит Петя, первый раз он всегда берет одну конфету, а каждый следующий раз - на одну больше, чем в предыдущий. Вася же каждый раз берет столько конфет, сколько Петя всего в сумме взял до этого. То есть во время первого хода Петя возьмет 1 конфету, затем во время второго хода Вася возьмет 1 конфету, потом Петя возьмет 2 конфеты, Вася возьмет 1 + 2 = 3 конфеты и т. д.

Поскольку ребята хотели поиграть в эту игру подольше, они придумали дополнительное правило — на каждом шаге нельзя брать из мешка больше чем M конфет. И теперь они хотят выбрать такое максимальное M, что конфет при этом хватит на S ходов игры. Помогите им это сделать.

Во время тура будут проверяться только примеры из условия, полная проверка будет выполнена после тура.

Формат входного файла

Первая строка входного файла содержит целые числа K и S — количество конфет и количество ходов соответственно.

Формат выходного файла

Выходной файл должен содержать единственное целое число M — такое максимальное количество конфет, чтобы игра продлилась хотя бы S ходов.

Ограничения

1 ≤ S ≤ K ≤ 10⁹, M ≤ K

Примеры тестов

6 4

2

14 6

4

Задача D. Антон и магазин радиодеталей ≡

Условие

Инженер Антон зашёл в магазин радиодеталей. В магазине ровно N стеллажей. На i-м стеллаже лежат радиодетали типа a_i (на двух различных стеллажах тип радиодеталей может повторяться). Антон обходит с тележкой стеллажи в порядке от первого до N-го.

Когда Антон подходит к очередному стеллажу, он смотрит в тележку. Если в тележке нет радиодеталей такого типа, как на стеллаже, Антон берёт деталь со стеллажа и складывает в тележку. Если радиодеталь такого типа в тележке уже лежит, Антон просто идет дальше.

Антон знает заранее, какие типы радиодеталей лежат на стеллажах, и хочет каждый раз выбрасывать из тележки такую деталь, чтобы как можно меньше раз складывать новые радиодетали в тележку (складывает он их только в случае, если таких деталей в тележке нет на данный момент).

Помогите Антону узнать, какое минимальное количество раз ему придётся складывать новую деталь в тележку.

Примечание

Рекомендуется рассмотреть частичные решения для N ≤ 1000, a_i ≤ 10⁵.

Формат входного файла

Входной файл содержит целое число два целых числа N и K, вторая строка содержит N чисел a_i.

Формат выходного файла

Выходной файл должен содержать единственное число — минимальное количество раз, которое придётся положить деталь в тележку.

Ограничения

1 ≤ N, K ≤ 10⁵

0 ≤ a_i ≤ 10⁹

Примеры тестов

3 3 
1 2 3

3

5 2
1 1 1 2 2

2

7 3
8 2 3 1 1 2 2

4