Given a directed graph with $n$ vertices and $m$ edges, where $s$ is the source and $t$ is the sink. Each edge has a starting vertex $a_i$, an ending vertex $b_i$, a lower bound on flow $l_i$, an upper bound on flow $u_i$, and a cost $c_i$.

You need to find a flow from $s$ to $t$ that satisfies the flow conservation at each vertex and the flow bounds on each edge, such that the cost is minimized while the flow is maximized.

Input

The first line contains four integers $n, m, s, t$.

The next $m$ lines each contain five integers $a_i, b_i, l_i, u_i, c_i$.

Output

If no valid flow exists, output a single integer -1.

Otherwise, output two integers on a single line: the first integer represents the maximum flow, and the second integer represents the minimum cost for that maximum flow.

Examples

Input 1

3 3 1 3
1 2 0 6 0
2 3 1 1000 4
2 3 0 1000 3

Output 1

6 19

Input 2

5 6 2 4
2 1 1 6 4
2 3 0 5 1
1 3 2 8 2
3 4 1 7 1
3 5 0 4 1
5 4 1 5 2

Output 2

11 60

Input 3

3 1 1 3
2 3 1 100 -100

Output 3

-1

Input 4

7 21 6 2
4 2 5838 564426 865577
2 4 138826 402418 671157
3 2 123701 426813 -543072
4 7 98453 297069 -986761
4 1 21240 326890 -393845
6 7 2698 993886 -59647
4 6 82877 385922 -912546
7 4 25734 366246 285364
7 1 69448 399825 -401006
3 6 22302 805072 919199
6 3 124308 353738 -384169
3 5 139305 535596 -570512
5 2 81261 479615 -662499
4 2 17109 716121 -195178
7 3 7838 518193 274351
6 4 60957 638462 -423334
7 2 56175 606681 -703583
6 3 35947 112359 -495175
1 3 90688 695522 618674
6 3 26527 999630 -429406
5 7 58044 610148 862096

Output 4

2313184 -1814133530696

Constraints

For all data, it is guaranteed that $1 \le n \le 1\,000$, $1 \le m \le 5\,000$, $1 \le s,t \le n$, and $s \ne t$.

For all data, it is guaranteed that $1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le l_i \le u_i \le 10^6$, and $-10^6 \le c_i \le 10^6$.

Specifically, the test data for this problem is generated as follows:

1. Select values for $n, m, s, t$ (not necessarily randomly).
2. Generate a directed graph $G$ with $m$ edges as follows:
   1. Select parameters $k_1, k_2$ such that $0 \le k_1, k_2$ and $k_1 + k_2 \le n$.
   2. Perform $k_1$ times:
      • Uniformly select $1 \le a \le n$ where $a \ne s$, and add an edge $s \to a$.
   3. Perform $k_2$ times:
      • Uniformly select $1 \le a \le n$ where $a \ne t$, and add an edge $a \to t$.
   4. Perform $m-k_1-k_2$ times:
      • Uniformly select $1 \le a, b \le n$ where $a \ne b$, and add an edge $a \to b$.
3. For each edge, uniformly select its cost $c_i \in [-10^6, 10^6]$.
4. For each edge, select a $\Delta_i \in [1, 10^6]$ (not necessarily randomly).
5. Randomly perform the following process several times:
   1. Select a value $\delta \in [1, 10^6]$ (not necessarily randomly).
   2. Perform a DFS from $s$ through the graph, choosing an outgoing edge uniformly at random each time.
   3. If the sink $t$ is reached, increase $l_i$ by $\delta$ for all edges on the path from $s$ to $t$.
   4. Specifically, if any edge's $l_i$ exceeds $10^6 - \Delta_i - \delta$, abort this operation.
6. Randomly perform the following process several times:
   1. Select a value $\delta \in [1, 10^6]$ (not necessarily randomly).
   2. Uniformly select a vertex $x$.
   3. Perform a DFS from $x$ through the graph, choosing an outgoing edge uniformly at random each time.
   4. If the vertex $x$ is reached again, increase $l_i$ by $\delta$ for all edges on the path.
   5. Specifically, if any edge's $l_i$ exceeds $10^6 - \Delta_i - \delta$, abort this operation.
7. Set $u_i = l_i + \Delta_i$ for each edge.