Задача A. Падал теплый свет ≡

Условие

В каждую комнату солнечный свет падает под углом 45 градусов через вертикальное окно. Окно заданной ширины расположено в одной из стен от пола до потолка.

Нужно посчитать освещенность каждой комнаты, если для каждой комнаты даны высота h и длина комнаты l, а также ширина окна w. Освещенностью комнаты называется площадь части стены напротив окна, освещенная солнцем.

Формат входных данных

Входные файл содержит одну строку с тремя целыми числами h, l и w.

Формат выходных данных

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

Ограничения

1 ≤ h, l, w ≤ 10⁴

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

4 2 3

6

2 4 3

0

Задача B. Имя для аллигатора ≡

Условие

Вася купил аллигатора и строку s, теперь он хочет выбрать для аллигатора имя, которое будет подстрокой строки s. Имя аллигатора не должно быть длиннее 100 символов или короче 5 символов.

Вася считает слогом пару букв, в которой первая буква согласная, а вторая гласная. Красотой имени называется количество слогов в имени.

Помогите Васе посчитать максимальную красоту имени для аллигатора.

Гласные буквы: A, E, I, O, U, Y

Согласные буквы: B, C, D, F, G, H, J, K, L, M, N, P, Q, R, S, T, V, W, X, Z

Формат входных данных

Первая строка входного файла содержит строку s.

Формат выходных данных

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

Ограничения

Длина строки s не превосходит 5 ⋅ 10⁴ и не меньше чем 5, строка состоит из заглавных букв.

Описание подзадач и системы оценивания

Решения работающие для длины s не превосходящей 10³ оцениваются из 40 баллов.

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

BOBIK

2

AYEAUEI

0

Задача C. Найм рабочих ≡

Условие

Прораб распланировал работы на n дней вперёд, в день i выполняется только один тип работ a_i и при этом требуется c_i работников. В компании нет постоянных сотрудников, каждый день нанимаются новые работники для выполнения работ.

Так же у прораба имеется список из m работников. j-й работник имеет компетенции на k_j различных работ и работник просит p_j денег за один день работы (в независимости от типа выполняемых работ).

Так как бюджет ограничен, прораб хочет узнать какое минимальное количество денег он может потратить в каждый из n дней при этом наняв нужное количество работников. Гарантируется, что работников всегда достаточно.

Формат входных данных

Первая строка входного файла содержит два целых числа n и m. Далее следует n строк содержащих по два целых числа a_i и c_i. Следующие m строк содержат два целых числа k_j и p_j, количество компетенций и зарплата за день сотрудника с номером j, далее в этой строке идут k_j чисел, номера работ которые может выполнять сотрудник с номером j.

Формат выходных данных

Выходной файл должен содержать n целых чисел, i-e число минимальное количество денег которое нужно потратить в день i.

Ограничения

0 ≤ n, m, k_i ≤ 10⁵; 1 ≤ a_i ≤ 10⁹; 1 ≤ p_i ≤ 100

Сумма по всем k_i не превосходит 2 ⋅ 10⁵.

Описание подзадач и системы оценивания

Решения работающие для 0 ≤ n, m, k_i ≤ 10³; 1 ≤ a_i, p_i ≤ 10³, сумма по всем k_i не превосходит 2 ⋅ 10³ оцениваются из 40 баллов.

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

5 3
1 1
2 1
3 1
1 3
1 2
3 100 1 2 3
3 10 1 2 3
1 1 1

1
10
10
111
11

1 4
229 4
2 23 1 229
2 22 4 229
2 11 229 15
3 21 65 43 229

77