Метелик#3594
Клер — справжня серцеїдка. Вона зустрічається з багатьма хлопцями і постійно ходить на побачення. Одного дня вона виявила конфлікти у своєму розкладі побачень. Ой!
Тепер їй потрібно вибрати деякі побачення і відмовитися від інших. Побачення заплановані на певні години, наприклад, з 13:00 до 15:00. Вона може мати кілька побачень з одним хлопцем. Наприклад, вона може зустрічатися з Адамом з 10:00 до 12:00 і з 14:00 до 16:00, а з Бобом з 12:00 до 13:00 і з 18:00 до 20:00. Вона може відвідати всі ці побачення, якщо вони не перетинаються за часом. Час на дорогу, макіяж, любовні трикутники та інші проблеми її не хвилюють. Таким чином, у наведеному прикладі вона може зберегти всі побачення з Адамом і Бобом. Всі побачення заплановані між 6:00 і 22:00 в один день.
Клер прагне отримати максимальне задоволення. Кожен хлопець приносить їй певне задоволення, якщо вона відвідає всі заплановані з ним побачення. Наприклад, задоволення від Адама становить , а від Боба . Оскільки вона може зустрітися з обома, вона може отримати задоволення загалом.
Ваше завдання — написати програму, яка допоможе їй у цьому. Можливо, тоді вона знайде час і для вас... якщо ви цього бажаєте.
Вхід складається з кількох наборів даних. Кожен набір даних має наступний формат:
\text{Guy}_1 \text{Guy}_N
Перший рядок входу містить ціле число (1 \leq N \leq 100), яке вказує кількість хлопців. Далі йдуть описи хлопців. Кожен опис має такий формат:
S_1 E_1 S_M E_M
Перший рядок містить два цілі числа M_i (1 \leq M_i \leq 16) і L_i (1 \leq L_i \leq 100000000), які вказують кількість побачень з хлопцем і задоволення, яке вона отримає від нього. Далі йдуть рядків. -й рядок містить два цілі числа S_i і E_i (6 \leq S_i < E_i \leq 22), які вказують час початку і закінчення -го побачення.
Кінець входу позначається N = 0.
Для кожного набору даних виведіть максимальну кількість задоволення, яку вона може отримати.
Приклад 1