C. Синхрофазотрон
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Для неких экспериментов маленькому Пете срочно понадобился синхрофазотрон. Сам прибор у Пети уже есть, осталось настроить подачу топлива к нему. Топливо поступает по системе узлов, пронумерованных числами от 1 до n, соединённых трубами. Трубы идут из каждого узла с меньшим номером в каждый узел с большим, топливо может идти по трубе только в направлении от узла с меньшим номером к узлу с большим. В первый узел может поступить любое количество топлива, а из последнего узла топливо поступает прямо в синхрофазотрон. Известно, что каждая из труб имеет три характеристики: минимальное количество топлива, которое должно по ней течь, максимальное число топлива, которое может по ней течь, и стоимость активации трубы. Если по трубе из узла i в узел j течет cij единиц топлива (cij > 0), то заплатить за это надо будет aij + cij2 тугриков (aij — стоимость активации этой трубы). Если же по трубе не течет топливо, то платить ничего нельзя. По трубам может течь только целое число единиц топлива.

Минимальное и максимальное ограничение на трубу действует всегда, а не только тогда когда она активирована. Считается, что труба активна тогда и только тогда, когда поток через это трубу строго больше нуля.

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

Входные данные

В первой строке находится целое число n (2 ≤ n ≤ 6) — количество узлов. В следующих n(n - 1) / 2 строках находятся пятерки целых чисел, s, f, l, h, a, описывающие трубы — начальный узел трубы, конечный узел трубы, минимальное и максимальное количество топлива, которое может течь по трубе, и стоимость активации трубы, соответственно. (1 ≤ s < f ≤ n, 0 ≤ l ≤ h ≤ 5, 0 ≤ a ≤ 6). Гарантируется, что во входных данных для каждой пары узлов с различными номерами будет описана ровно одна труба между ними.

Выходные данные

Выведите в первую строку два числа через пробел: минимальное возможное количество топлива, которое может течь в синхрофазотрон, и максимальную возможную сумму, которую надо будет потратить на то, чтобы это количество топлива достигло синхрофазотрона. Если не существует количества топлива, которое могло бы достичь синхрофазотрона, выведите "-1 -1".

Количество топлива, которое достигнет синхрофазотрона, не обязано быть положительным — оно может равняться нулю, если минимальные ограничения на количество топлива у всех труб равны нулю.

Примеры
Входные данные
2
1 2 1 2 3
Выходные данные
1 4
Входные данные
3
1 2 1 2 3
1 3 0 0 0
2 3 3 4 5
Выходные данные
-1 -1
Входные данные
4
1 2 0 2 1
2 3 0 2 1
1 3 0 2 6
1 4 0 0 1
2 4 0 0 0
3 4 2 3 0
Выходные данные
2 15
Входные данные
3
1 2 0 2 1
1 3 1 2 1
2 3 1 2 1
Выходные данные
2 6
Примечание

В первом тесте мы можем пустить 1 или 2 единицы топлива по трубе из 1 в 2. Минимальное возможное количество — 1, пустить его стоит a12 + 12 = 4.

Во втором тесте, мы можем пустить максимум 2 единицы из узла 1 в узел 2, и нам нужно пустить как минимум 3 единицы из узла 2 в узел 3. Это невозможно.

В третьем тесте минимальное возмножное количество равно 2. Мы можем пустить каждую единицу топлива по одному из двух путей: 1->2->3->4 или 1->3->4. Если мы дважды воспользуемся первым путем, это будет стоить a12 + 22 + a23 + 22 + a34 + 22=14. Если мы дважды воспользуемся вторым путем, это будет стоить a13 + 22 + a34 + 22=14. Однако если мы воспользуемся каждым путем (разрешив 1 единице топлива течь по трубам 1->2, 2->3, 1->3 и двум единицам по трубе 3->4), это будет стоить a12 + 12 + a23 + 12 + a13 + 12 + a34 + 22=15 и это максимальная возможная цена.

Заметим также, что по ребру 1->4 ничего не течет, по-этому стоимость его активации к ответу не прибавляется.