Mirko's Advantage Race

Mirko and Slvako are participating in a high‐speed race. The race map contains \( N \) villages and \( M \) roads. For the \( i\)-th road, two parameters \( M_i \) and \( S_i \) are given, representing the time taken by Mirko and Slvako respectively when traversing that road.

The race starts and finishes at the same village. A route is defined as a cycle (a path that starts and ends at the same village without repeating any other village). Let \( X \) be the total time for Mirko along the route and \( Y \) be the total time for Slvako. Your task is to find a route which, firstly, uses as few villages as possible and, secondly, among those, maximizes the advantage \( Y - X \) (i.e. the difference between Slvako's and Mirko's time).

If no valid route exists, output -1.

Note: All equations are formatted in LaTeX. The difference for a route is computed as \(\sum (S_i - M_i)\) over all roads in the cycle.

inputFormat

The first line contains two integers \( N \) and \( M \) where \( 1 \leq N \leq 15 \) (assumed small for exponential search) and \( M \) is the number of roads.

Each of the following \( M \) lines contains four integers: \( u\), \( v \), \( M_i \) and \( S_i \) meaning there is an undirected road between villages \( u \) and \( v \) with travel times \( M_i \) (for Mirko) and \( S_i \) (for Slvako). It is guaranteed that \( u \) and \( v \) are between 1 and \( N \).

You may assume that there are no multiple edges and no self-loops.

outputFormat

If a valid route (cycle) exists, print two space‐separated integers: the minimum number of villages in the route and the maximum possible advantage \( Y - X \) achievable among all cycles with that many villages.

If no valid route exists, output -1.

sample

4 4
1 2 3 5
2 3 2 7
3 1 4 8
3 4 1 2

3 11