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

Кроме того, определённые плюсы есть у друзей, с которыми он готов разделить крышу над головой. Например, Игорь хорошо готовит, Дима — аккуратный, а Костя и готовит, и сможет объяснить, как решать задачи по функциональному анализу. Не надо забывать, что свои плюсы есть и у жизни в одиночестве.

Женя уже составил список из подходящих квартир и возможных соседей и оценил в условных единицах преимущества каждой квартиры и каждого друга, а также преимущества жизни одному. Кроме того, он знает, какую максимальную сумму он готов отдавать за жильё и сколько готов платить каждый друг из его списка. Помогите Жене принять решение.

В первой строке записаны три целых числа — максимальная сумма, которую Женя готов платить за один месяц, преимущества жизни одному в однокомнатной квартире и преимущества жизни одному в двухкомнатной квартире.

Во второй строке записано целое число 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.»

В первом примере у Жени не хватает денег на вторую квартиру даже вместе с другом. Поэтому он вынужден снять первую, сумма преимуществ в этом случае будет 250 (50 + 200).

Во втором примере у Жени хватает денег на любую квартиру, но вместе с другом он сможет жить только в третьей квартире. Если выбрать этот вариант, сумма преимуществ будет 2002 (1001 + 1001), а если жить одному, то не более 2001 (1 + 2000, если жить одному во второй квартире).

В третьем примере у Жени не хватает денег на единственный возможный вариант.