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