Có \(N\) thành phố và \(M\) tuyến đường mà các bưu kiện có thể được vận chuyển từ thành phố này sang thành phố khác. Với mỗi tuyến đường, biết được số bưu kiện có thể vận chuyển và chi phí của một bưu kiện.Tìm ra số cách rẻ nhất để gửi \(K\) bưu kiện từ Syrjälä đến Lehmälä.

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\) : số thành phố, tuyến đường và bưu kiện. Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä và thành phố \(N\) là Lehmälä.
• \(M\) dòng sau mô tả các tuyến đường. Mỗi dòng gồm bốn số nguyên \(a\), \(b\), \(r\) và \(c\) : tuyến đường từ \(a\) đến \(b\) vận chuyển tối đa \(r\) bưu kiện và chi phí mỗi bưu kiện là \(c\).

Output

• In ra một số nguyên: Chi phí tối thiểu hoặc \(-1\) nếu không có đáp án.

Constraints

• \(1 \ \leq \ N \ \leq \ 500\)
• \(1 \ \leq \ M \ \leq \ 1000\)
• \(1 \ \leq \ K \ \leq \ 100\)
• \(1 \ \leq a, b \ \leq \ n\)
• \(1 \ \leq r, c \ \leq \ 1000\)

Example

Sample input

4 5 3
1 2 5 100
1 3 10 50
1 4 7 500
2 4 8 350
3 4 2 100

750

Note

• Explanation:
• Một bưu kiện được vận chuyển qua tuyến đường: \(1 \rightarrow 2 \rightarrow 4\) \((1 \times 450 = 450).\)
• Hai bưu kiện được vận chuyển qua tuyến đường: \(1 \rightarrow 3 \rightarrow 4\) \((2 \times 150 = 300).\)