Для неких экспериментов маленькому Пете срочно понадобился синхрофазотрон. Сам прибор у Пети уже есть, осталось настроить подачу топлива к нему. Топливо поступает по системе узлов, пронумерованных числами от 1 до n, соединённых трубами. Трубы идут из каждого узла с меньшим номером в каждый узел с большим, топливо может идти по трубе только в направлении от узла с меньшим номером к узлу с большим. В первый узел может поступить любое количество топлива, а из последнего узла топливо поступает прямо в синхрофазотрон. Известно, что каждая из труб имеет три характеристики: минимальное количество топлива, которое должно по ней течь, максимальное число топлива, которое может по ней течь, и стоимость активации трубы. Если по трубе из узла i в узел j течет cij единиц топлива (cij > 0), то заплатить за это надо будет aij + cij2 тугриков (aij — стоимость активации этой трубы). Если же по трубе не течет топливо, то платить ничего нельзя. По трубам может течь только целое число единиц топлива.
Минимальное и максимальное ограничение на трубу действует всегда, а не только тогда когда она активирована. Считается, что труба активна тогда и только тогда, когда поток через это трубу строго больше нуля.
Петя не хочет, чтобы система труб была слишком перегружена, поэтому он хочет найти минимальное количество топлива, которое, поступив в первый узел, сможет достигнуть синхрофазатрона. При этом он хочет впечатлить спонсоров, поэтому суммарная стоимость, которую нужно будет заплатить за прохождение топлива по всем трубам, должна быть максимальна.
Выходные данные
Выведите в первую строку два числа через пробел: минимальное возможное количество топлива, которое может течь в синхрофазотрон, и максимальную возможную сумму, которую надо будет потратить на то, чтобы это количество топлива достигло синхрофазотрона. Если не существует количества топлива, которое могло бы достичь синхрофазотрона, выведите "-1 -1".
Количество топлива, которое достигнет синхрофазотрона, не обязано быть положительным — оно может равняться нулю, если минимальные ограничения на количество топлива у всех труб равны нулю.
Примечание
В первом тесте мы можем пустить 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 ничего не течет, по-этому стоимость его активации к ответу не прибавляется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2 1 2 3
|
1 4
|
|
2
|
3
1 2 1 2 3
1 3 0 0 0
2 3 3 4 5
|
-1 -1
|
|
3
|
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
|
|
4
|
3
1 2 0 2 1
1 3 1 2 1
2 3 1 2 1
|
2 6
|