h2. Restrictii

* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 30 000$

* $1 ≤ N ≤ 700$
* $1 ≤ M ≤ 131 072$

* $1 ≤ S ≤ M$
* $pe un drum pot fi plasati oricati soldati$

* $lungimila unui drum nu depaseste 5 000$
* $veti primi punctaj maxim pe un test doar daca diferenta dintre raspunsul oficial si raspusul dumneavoastra este ≤ 10 ^-4^  $

* $lungimila unui drum nu depaseste 100 000$
* $punctajul se va acorda in functie de diferenta absoluta dintre raspunsul dumneavoastra si raspunsul comisiei:$
** $10 puncte/test daca diferenta ≤ 0.1$
** $5 puncte/test daca diferenta ≤ 34.5$
** $3 puncte/test daca diferenta ≤ 69$
** $1 punct/test daca diferenta ≤ 103.5$
** $0 puncte/test daca diferenta este > 103.5$

h2. Exemplu