Існує \(n\) міст і \(m\) маршрутів, якими посилки можна доставити з одного міста в інше. Для кожного маршруту ви знаєте максимальну кількість посилок і вартість однієї посилки.

Ви хочете надіслати \(k\) посилок із A до B. Як це зробити найдешевше?

Обмеження

• \(2≤n≤500\)
• \(1≤m≤1000\)
• \(1≤k≤100\)
• \(1≤a,b≤n\)
• \(1≤r,c≤1000\)

Формат вхідних даних

У першому рядку є три цілі числа \(n\), \(m\) і \(k\): кількість міст, маршрутів і посилок. Міста пронумеровані цифрами \(1,2,…,n\). Місто 1 – A, а місто \(n\) – B.

Після цього іде \(m\) рядків, які описують маршрути. Кожен рядок містить чотири цілі числа \(a\), \(b\), \(r\) і \(c\): є маршрут з міста \(a\) до міста \(b\), максимум \(r\) посилок може перевозити по маршруту, а вартість кожної посилки становить \(c\).

Формат вихідних даних

Вивести одне ціле число: мінімальну загальну вартість або −1, якщо розв'язків немає.

Пояснення:

одна посилка доставляється маршрутом 1→2→4 (варт 1⋅450=450) і маршрутом доставлено дві посилки 1→3→4 (варт 2⋅150=300).

Приклад вхідних даних

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

Приклад вихідних даних

750