For some experiments little Petya needs a synchrophasotron. He has already got the device, all that's left is to set the fuel supply. Fuel comes through a system of nodes numbered from 1 to n and connected by pipes. Pipes go from every node with smaller number to every node with greater number. Fuel can only flow through pipes in direction from node with smaller number to node with greater number. Any amount of fuel can enter through the first node and the last node is connected directly to the synchrophasotron. It is known that every pipe has three attributes: the minimum amount of fuel that should go through it, the maximum amount of fuel that can possibly go through it and the cost of pipe activation. If cij units of fuel (cij > 0) flow from node i to node j, it will cost aij + cij2 tugriks (aij is the cost of pipe activation), and if fuel doesn't flow through the pipe, it doesn't cost anything. Only integer number of units of fuel can flow through each pipe.

Constraints on the minimal and the maximal fuel capacity of a pipe take place always, not only if it is active. You may assume that the pipe is active if and only if the flow through it is strictly greater than zero.

Petya doesn't want the pipe system to be overloaded, so he wants to find the minimal amount of fuel, that, having entered the first node, can reach the synchrophasotron. Besides that he wants to impress the sponsors, so the sum of money needed to be paid for fuel to go through each pipe, must be as big as possible.

Input

First line contains integer n (2 ≤ n ≤ 6), which represents the number of nodes. Each of the next n(n - 1) / 2 lines contains five integers s, f, l, h, a that describe pipes — the first node of the pipe, the second node of the pipe, the minimum and the maximum amount of fuel that can flow through the pipe and the the activation cost, respectively. (1 ≤ s < f ≤ n, 0 ≤ l ≤ h ≤ 5, 0 ≤ a ≤ 6). It is guaranteed that for each pair of nodes with distinct numbers there will be exactly one pipe between them described in the input.

Output

Output in the first line two space-separated numbers: the minimum possible amount of fuel that can flow into the synchrophasotron, and the maximum possible sum that needs to be paid in order for that amount of fuel to reach synchrophasotron. If there is no amount of fuel that can reach synchrophasotron, output "-1 -1".

The amount of fuel which will flow into synchrophasotron is not neccessary positive. It could be equal to zero if the minimum constraint of every pipe is equal to zero.

Examples

Input

2
1 2 1 2 3


Output

1 4


Input

3
1 2 1 2 3
1 3 0 0 0
2 3 3 4 5


Output

-1 -1


Input

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


Output

2 15


Input

3
1 2 0 2 1
1 3 1 2 1
2 3 1 2 1


Output

2 6

Note

In the first test, we can either pass 1 or 2 units of fuel from node 1 to node 2. The minimum possible amount is 1, it costs a12 + 12 = 4.

In the second test, you can pass at most 2 units from node 1 to node 2, and at you have to pass at least 3 units from node 2 to node 3. It is impossible.

In the third test, the minimum possible amount is 2. You can pass each unit of fuel through two different paths: either 1->2->3->4 or 1->3->4. If you use the first path twice, it will cost a12 + 22 + a23 + 22 + a34 + 22=14. If you use the second path twice, it will cost a13 + 22 + a34 + 22=14. However, if you use each path (allowing one unit of fuel go through pipes 1->2, 2->3, 1->3, and two units go through 3->4) it will cost a12 + 12 + a23 + 12 + a13 + 12 + a34 + 22=15 and it is the maximum possible cost.

Also note that since no fuel flows from node 1 to node 4, activation cost for that pipe is not added to the answer.
import java.io.*;
import java.math.BigInteger;
import java.util.*;

/**
 * @author Egor Kulikov (egor@egork.net)
 */
public class TaskC {
	@SuppressWarnings({"FieldCanBeLocal", "UnusedDeclaration"})
	private final InputReader in;
	private final PrintWriter out;
	private final boolean testMode;
	private Map<State,Integer> map;
	private int[][] activation, low, high;

	private static class State {
		private final int[] flow;
		private final int currentIndex;

		private State(int[] flow, int currentIndex) {
			this.flow = flow;
			this.currentIndex = currentIndex;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;
			if (o == null || getClass() != o.getClass())
				return false;

			State state = (State) o;

			if (currentIndex != state.currentIndex)
				return false;
			if (!Arrays.equals(flow, state.flow))
				return false;

			return true;
		}

		@Override
		public int hashCode() {
			int result = flow != null ? Arrays.hashCode(flow) : 0;
			result = 31 * result + currentIndex;
			return result;
		}
	}

	private void solve() {
		int n = in.readInt();
		int edgeCount = n * (n - 1) / 2;
		int[] from = new int[edgeCount];
		int[] to = new int[edgeCount];
		int[] low = new int[edgeCount];
		int[] high = new int[edgeCount];
		int[] activation = new int[edgeCount];
		in.readIntArrays(from, to, low, high, activation);
		int[] balance = new int[n];
		int[] currentCost = new int[edgeCount];
		int totalFlow = 0;
		int totalCost = 0;
		int[] remainingFlow = new int[edgeCount];
		this.activation = new int[n][n];
		this.low = new int[n][n];
		this.high = new int[n][n];
		for (int i = 0; i < edgeCount; i++) {
			from[i]--;
			to[i]--;
			this.activation[from[i]][to[i]] = activation[i];
			this.low[from[i]][to[i]] = low[i];
			this.high[from[i]][to[i]] = high[i];
		}
		State start = new State(new int[n], 1);
		map = new HashMap<State, Integer>();
		for (int i = 0; i <= (n - 1) * 5; i++) {
			start.flow[0] = i;
			int result = go(start, 0);
			if (result != -1) {
				out.println(i + " " + result);
				return;
			}
		}
		out.println("-1 -1");
	}

	private int go(State current, int index) {
		if (map.containsKey(current))
			return map.get(current);
		if (current.flow.length == 1) {
			map.put(current, 0);
			return 0;
		}
		if (current.currentIndex == current.flow.length) {
			if (current.flow[0] == 0) {
				State next = new State(new int[current.flow.length - 1], 1);
				System.arraycopy(current.flow, 1, next.flow, 0, next.flow.length);
				int result = go(next, index + 1);
				map.put(current, result);
				return result;
			}
			map.put(current, -1);
			return -1;
		}
		int result = -1;
		for (int i = low[index][index + current.currentIndex]; i <= high[index][index + current.currentIndex]; i++) {
			if (i > current.flow[0])
				break;
			State next = new State(new int[current.flow.length], current.currentIndex + 1);
			System.arraycopy(current.flow, 0, next.flow, 0, next.flow.length);
			next.flow[0] -= i;
			next.flow[current.currentIndex] += i;
			int currentResult = go(next, index);
			if (currentResult != -1)
				result = Math.max(result, currentResult + i * i + (i == 0 ? 0 : activation[index][index + current.currentIndex]));
		}
		map.put(current, result);
		return result;
	}

	private static List<Test> createTests() {
		List<Test> tests = new ArrayList<Test>();
		tests.add(new Test("3\n" +
				"1 2 0 2 1\n" +
				"1 3 1 2 1\n" +
				"2 3 1 2 1", "2 6"));
		tests.add(new Test("2\n" +
				"1 2 1 2 3", "1 4"));
		tests.add(new Test("3\n" +
				"1 2 1 2 3\n" +
				"1 3 0 0 0\n" +
				"2 3 3 4 5", "-1 -1"));
		tests.add(new Test("4\n" +
				"1 2 0 2 1\n" +
				"2 3 0 2 1\n" +
				"1 3 0 2 6\n" +
				"1 4 0 0 1\n" +
				"2 4 0 0 0\n" +
				"3 4 2 3 0", "2 15"));
//		tests.add(new Test("", ""));
//		tests.add(new Test("", ""));
//		tests.add(new Test("", ""));
//		tests.add(new Test("", ""));
//		tests.add(new Test("", ""));
//		tests.add(new Test("", ""));
		return tests;
	}

	private void run() {
		//noinspection InfiniteLoopStatement
//		while (true)
//		int testCount = in.readInt();
//		for (int i = 0; i < testCount; i++)
		solve();
		exit();
	}

	private TaskC() {
		@SuppressWarnings({"UnusedDeclaration"})
		String id = getClass().getName().toLowerCase();
		//noinspection EmptyTryBlock
		try {
//			System.setIn(new FileInputStream(id + ".in"));
//			System.setOut(new PrintStream(new FileOutputStream(id + ".out")));
//			System.setIn(new FileInputStream("input.txt"));
//			System.setOut(new PrintStream(new FileOutputStream("output.txt")));
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
		in = new StreamInputReader(System.in);
		out = new PrintWriter(System.out);
		testMode = false;
	}

	@SuppressWarnings({"UnusedParameters"})
	private static String check(String input, String result, String output) {
//		return strictCheck(result, output);
		return tokenCheck(result, output);
	}

	public static void main(String[] args) {
		if (args.length != 0 && args[0].equals("42"))
			test();
		else
			new TaskC().run();
	}

	private static void test() {
		List<Test> tests = createTests();
		int testCase = 0;
		for (Test test : tests) {
			System.out.print("Test #" + testCase + ": ");
			InputReader in = new StringInputReader(test.getInput());
			StringWriter out = new StringWriter(test.getOutput().length());
			long time = System.currentTimeMillis();
			try {
				new TaskC(in, new PrintWriter(out)).run();
			} catch (TestException e) {
				time = System.currentTimeMillis() - time;
				String checkResult = check(test.getInput(), out.getBuffer().toString(), test.getOutput());
				if (checkResult == null)
					System.out.print("OK");
				else
					System.out.print("WA (" + checkResult + ")");
				System.out.printf(" in %.3f s.\n", time / 1000.);
			} catch (Throwable e) {
				System.out.println("Exception thrown:");
				e.printStackTrace(System.out);
			}
			testCase++;
		}
	}

	private static String tokenCheck(String result, String output) {
		StringInputReader resultStream = new StringInputReader(result);
		StringInputReader outputStream = new StringInputReader(output);
		int index = 0;
		boolean readingResult = false;
		try {
			while (true) {
				readingResult = true;
				String resultToken = resultStream.readString();
				readingResult = false;
				String outputToken = outputStream.readString();
				if (!resultToken.equals(outputToken))
					return "'" + outputToken + "' expected at " + index + " but '" + resultToken + "' received";
				index++;
			}
		} catch (InputMismatchException e) {
			if (readingResult) {
				try {
					outputStream.readString();
					return "only " + index + " tokens received";
				} catch (InputMismatchException e1) {
					return null;
				}
			} else
				return "only " + index + " tokens expected";
		}
	}

	@SuppressWarnings({"UnusedDeclaration"})
	private static String strictCheck(String result, String output) {
		if (result.equals(output))
			return null;
		return "'" + output + "' expected but '" + result + "' received";
	}

	@SuppressWarnings({"UnusedDeclaration"})
	private static boolean isDoubleEquals(double expected, double result, double certainty) {
		return Math.abs(expected - result) < certainty || Math.abs(expected - result) < certainty * expected;
	}

	private TaskC(InputReader in, PrintWriter out) {
		this.in = in;
		this.out = out;
		testMode = true;
	}

	@SuppressWarnings({"UnusedDeclaration"})
	private void exit() {
		out.close();
		if (testMode)
			throw new TestException();
		System.exit(0);
	}

	private static class Test {
		private final String input;
		private final String output;

		private Test(String input, String output) {
			this.input = input;
			this.output = output;
		}

		public String getInput() {
			return input;
		}

		public String getOutput() {
			return output;
		}
	}

	@SuppressWarnings({"UnusedDeclaration"})
	private abstract static class InputReader {
		public abstract int read();

		public int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long readLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuffer res = new StringBuffer();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private String readLine0() {
			StringBuffer buf = new StringBuffer();
			int c = read();
			while (c != '\n' && c != -1) {
				if (c != '\r')
					buf.appendCodePoint(c);
				c = read();
			}
			return buf.toString();
		}

		public String readLine() {
			String s = readLine0();
			while (s.trim().length() == 0)
				s = readLine0();
			return s;
		}

		public String readLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines)
				return readLine();
			else
				return readLine0();
		}

		public BigInteger readBigInteger() {
			try {
				return new BigInteger(readString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}

		public char readCharacter() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			return (char) c;
		}

		public double readDouble() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, readInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}

		public int[] readIntArray(int size) {
			int[] array = new int[size];
			for (int i = 0; i < size; i++)
				array[i] = readInt();
			return array;
		}

		public long[] readLongArray(int size) {
			long[] array = new long[size];
			for (int i = 0; i < size; i++)
				array[i] = readLong();
			return array;
		}

		public double[] readDoubleArray(int size) {
			double[] array = new double[size];
			for (int i = 0; i < size; i++)
				array[i] = readDouble();
			return array;
		}

		public String[] readStringArray(int size) {
			String[] array = new String[size];
			for (int i = 0; i < size; i++)
				array[i] = readString();
			return array;
		}

		public char[][] readTable(int rowCount, int columnCount) {
			char[][] table = new char[rowCount][columnCount];
			for (int i = 0; i < rowCount; i++) {
				for (int j = 0; j < columnCount; j++)
					table[i][j] = readCharacter();
			}
			return table;
		}

		public void readIntArrays(int[]... arrays) {
			for (int i = 0; i < arrays[0].length; i++) {
				for (int j = 0; j < arrays.length; j++)
					arrays[j][i] = readInt();
			}
		}
	}

	private static class StreamInputReader extends InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;

		public StreamInputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	}

	private static class StringInputReader extends InputReader {
		private Reader stream;
		private char[] buf = new char[1024];
		private int curChar, numChars;

		public StringInputReader(String stream) {
			this.stream = new StringReader(stream);
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	}

	private static class TestException extends RuntimeException {}
}
