Giao Hàng

Có $n$ thành phố và $m$ tuyến đường. Bạn cần vận chuyển $k$ kiện hàng từ thành phố $1$ đến thành phố $n$.

Mỗi tuyến đường từ thành phố $a$ đến thành phố $b$ có thể vận chuyển tối đa $r$ kiện hàng, và chi phí vận chuyển là $c$ đồng cho mỗi kiện. Hãy tìm tổng chi phí vận chuyển nhỏ nhất để chuyển đủ $k$ kiện hàng.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n$, $m$, $k$ — số thành phố, số tuyến đường, và số kiện hàng cần vận chuyển.

• $m$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $a$, $b$, $r$, $c$ — mô tả tuyến đường từ $a$ đến $b$ với sức chứa tối đa $r$ kiện và chi phí $c$ đồng/kiện.

Dữ liệu ra

In một số nguyên duy nhất là tổng chi phí vận chuyển nhỏ nhất, hoặc $-1$ nếu không thể vận chuyển đủ $k$ kiện hàng.

Ràng buộc

• $2\le n\le 500$
• $1\le m\le 1000$
• $1\le k\le 100$
• $1\le a,b\le n$
• $1\le r,c\le 1000$

Ví dụ