Cho một đồ thị trong đó mỗi cạnh có dung lượng và chi phí, một mức phí cụ thể phải trả cho việc sử dụng một đơn vị lưu lượng trên mỗi cạnh. Biết đỉnh bắt đầu là ~1~ và đỉnh kết thúc là ~n~, hãy tìm luồng cực đại của đồ thị (dung lượng) và mức phí tối thiểu phải trả cho luồng cực đại đó.

Input

• Hai số nguyên ~n~ và ~m~ ở dòng đầu tiên cho biết đồ thị có ~n~ đỉnh và ~m~ cạnh.
• Từ dòng thứ hai đến ~m~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên ~s_i, t_i, c_i, w_i~ là một cạnh của đồ thị nối từ ~s_i~ đến ~t_i~, dung lượng là ~c_i~ và phí phải trả cho mỗi đơn vị lưu lượng là ~w_i~.

Output

Một hàng gồm hai số nguyên, tương ứng biểu thị lưu lượng tối đa và phí tối thiểu phải trả cho lưu lượng tối đa.

Sample

Input #1

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

Output #1

6 24

Ràng buộc

~1 \leq n \leq 400, 0 \leq m \leq 15000, w_i\geq 0~, biết rằng dữ liệu đầu vào, kết quả trung gian và câu trả lời nằm trong phạm vi số nguyên có dấu 32 bit.