Live Mercurian Navigation#12833

Live Mercurian Navigation

У 2121, на Меркурію, є меркуріанських міст та направлених доріг між цими містами. -а дорога йде з a_i-го міста до b_i-го міста. Для кожної пари міст та , є не більше одної дороги з до .

Рух на Меркурії стає важчим, вартість доріг також змінюється. У момент треба сплатити (c_i \cdot t + d_i) доларів, щоб проїхати по -й дорозі.

Bytica живе у -му місті та хоче поїхати у -те місто, отже вона використовує oo-машину для цього. Вона хоче знати приблизну кількість грошей, що вона має витратити, щоб дістатись з міста до міста у t \in [0, T].

Зауважте, що оскільки меркуріанські oo-машини є дуже швидкими, подорож по дорозі є миттєвою, тобто не займає час Bytica.

Формально, якщо це мінімальна сума грошей, що вона має витратити, щоб дістатись з міста до міста у час , Bytica хоче знайти

\frac{\int_0^{T} f(t) \mathrm{d}t}{T}.

Вхідні дані

Перший рядок містить цілих n, m, T (2 \leq n \leq 10, 1 \leq m \leq n(n - 1), 1 \leq T \leq 10^4).

-й з наступних рядків містить цілих a_i, b_i, c_i, d_i (1 \leq a_i, b_i \leq n, a_i \neq b_i, 0 \leq c_i, d_i \leq 10^3).

Гарантується, що Bytica може проїхати з міста до міста .

Вихідні дані

Надрукуйте дійсне число, що є відповіддю. Воно буде вважатись вірним якщо абсолютна або відносна похибка не перевищує 10^{-6}.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading