14077번 - Parada 다국어

Mirka je oduševila vojna parada prošle godine, a najviše su ga se dojmili, naravno, tenkovi. Zbog toga je odlučio aktivno sudjelovati u organizaciji iste iduće godine. Parada će se odvijati kao procesija kroz grad gdje se sve vojne postrojbe, uključujući i tenkove, kreću redom po unaprijed odabranim prometnicama bez vraćanja na isto mjesto.

Mirkov je osobni cilj da na paradi bude što je moguće više tenkova (označimo taj broj sa T). Međutim, problem s tenkovima je da su teški pa uništavaju prometnice po kojima prolaze. Sve su prometnice dvosmjerne i svaka povezuje dva raskrižja, a za prometnicu i je poznato koliko tenkova može proći po njoj (označimo taj broj sa T_i) prije nego što će je trebati početi popravljati. Nakon toga, cijena popravka te prometnice raste kvadratno s brojem tenkova, odnosno jednaka je C_i*(T-T_i)² tisuća kuna, gdje je C_i koeficijent cijene popravka prometnice.

Na sreću, postoji godišnji budžet od K tisuća kuna za obnovu prometnica koji se može ciljano iskoristiti upravo za obnovu prometnica po kojima će prolaziti tenkovi. Mirku stoga treba pomoć u organzaciji rute po kojoj će se kretati parada tako da se maksimizira broj tenkova, a da se ne prekorači budžet za popravak prometnica. Dodatno je ograničenje da parada mora početi na raskrižju 1, završiti na raskrižju N, a zajamčeno je da će postojati barem jedan takav put. 

U prvome retku nalaze se prirodni brojevi N, M i K (2 ≤ N ≤ 100 000, N-1 ≤ M ≤ 100 000, 1 ≤ K ≤ 10⁹ ), broj raskrižja, broj prometnica i budžet u tisućama kuna.

U idućih M redaka nalaze se po četiri cijela broja: A_i, B_i, C_i i T_i (1 ≤ A_i < B_i ≤ N, 1 ≤ C_i, T_i ≤ 1000), redom raskrižja koje povezuje prometnica i, faktor težine popravka te broj tenkova koji može po njoj proći bez potrebe za popravljanjem. Ne postoji više od jedne prometnice koje povezuje dva raskrižja. 

Potrebno je ispisati koliko najviše tenkova može sudjelovati na paradi tako da popravak ne košta više od predviđenog budžeta K.