ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2015. Женя переезжает из общежития

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
После переезда от родителей Женя уже месяц живёт в общежитии университета. Однако комендантский час и очередь в душ ему порядком надоели, и он захотел снять квартиру. Сделать выбор оказалось не так-то просто. Можно жить в однокомнатной или двухкомнатной квартире. Одному или с другом. Самостоятельно он сможет арендовать любую квартиру, а на двоих — только двухкомнатную. Если квартиру снимают двое, каждый платит ровно половину. У каждой квартиры есть ряд преимуществ, которые Женя обязательно будет учитывать, принимая решение: район, этаж, вид из окон и т.д.
Кроме того, определённые плюсы есть у друзей, с которыми он готов разделить крышу над головой. Например, Игорь хорошо готовит, Дима — аккуратный, а Костя и готовит, и сможет объяснить, как решать задачи по функциональному анализу. Не надо забывать, что свои плюсы есть и у жизни в одиночестве.
Женя уже составил список из подходящих квартир и возможных соседей и оценил в условных единицах преимущества каждой квартиры и каждого друга, а также преимущества жизни одному. Кроме того, он знает, какую максимальную сумму он готов отдавать за жильё и сколько готов платить каждый друг из его списка. Помогите Жене принять решение.

Исходные данные

В первой строке записаны три целых числа — максимальная сумма, которую Женя готов платить за один месяц, преимущества жизни одному в однокомнатной квартире и преимущества жизни одному в двухкомнатной квартире.
Во второй строке записано целое число n — количество друзей Жени (0 ≤ n ≤ 256). В следующих n строках следуют описания друзей, по два целых числа в каждой строке — максимальная сумма, которую друг готов платить за один месяц, и преимущества жизни вместе с ним.
В следующей строке записано целое число m — количество квартир (1 ≤ m ≤ 256). В следующих m строках следуют описания квартир, по три целых числа в каждой строке — количество комнат в квартире (1 или 2), арендная плата за неё в месяц и преимущества жизни в ней.
Все преимущества измеряются в одинаковых условных единицах и лежат в пределах от 0 до 100 000. Все денежные суммы измеряются в рублях и лежат в пределах от 1 до 100 000.

Результат

Выведите вариант с наибольшей суммой преимуществ, на который хватит денег у Жени (и у его друга, если он должен жить вместе с другом). Если Женя должен снимать квартиру с номером i в одиночку, выведите «You should rent the apartment #i alone.» Если Женя должен снимать квартиру с номером i вместе с другом j, выведите «You should rent the apartment #i with the friend #j.» Друзья и квартиры нумеруются с единицы в том порядке, в котором они даны на входе. Если существует несколько оптимальных вариантов, выведите любой из них. Если Женя не может снять никакую квартиру ни в одиночку, ни с другом, выведите «Forget about apartments. Live in the dormitory.»

Примеры

исходные данныерезультат
10000 50 70
1
10000 100
2
1 10000 200
2 30000 500
You should rent the apartment #1 alone.
30000 0 1
1
10000 1001
3
1 20000 2000
2 30000 2000
2 10000 1001
You should rent the apartment #3 with the friend #1.
1000 0 0
0
1
1 10000 1000
Forget about apartments. Live in the dormitory.

Замечания

В первом примере у Жени не хватает денег на вторую квартиру даже вместе с другом. Поэтому он вынужден снять первую, сумма преимуществ в этом случае будет 250 (50 + 200).
Во втором примере у Жени хватает денег на любую квартиру, но вместе с другом он сможет жить только в третьей квартире. Если выбрать этот вариант, сумма преимуществ будет 2002 (1001 + 1001), а если жить одному, то не более 2001 (1 + 2000, если жить одному во второй квартире).
В третьем примере у Жени не хватает денег на единственный возможный вариант.
Автор задачи: Евгений Курпилянский
Источник задачи: NEERC 2014, Четвертьфинал Восточного подрегиона