Problem D
Geezer Scripts

Um daginn var Unnar að spila Geezer Scripts, Geezer Scripts V til þess að fara rétt með hlutina. Hann opnaði dyr og áður en hann vissi af var hann kominn niður í stórt og flókið hellakerfi sem er fullt af andstæðingum sem munu ráðast á hann um leið og hann kemur nálægt þeim. Það sem verra er er að leikurinn geymir ekki hverja andstæðinga hann er búinn að sigra svo ef hann fer að andstæðingi og kemur aftur seinna þá þarf hann að berjast við andstæðinginn aftur! Þar sem hann er svolítill rati vill hann því biðja um aðstoð þína við að finna leiðina í gegnum hellana sem lætur hann verða sem fyrir sem minnstum skaða frá andstæðingunum.

Karakterinn hans Unnars hefur eitthvað skaðagildi $A$ og einhvern fjölda heilsustiga $H$. Slíkt hið sama gildir um andstæðingana. Þegar hann berst við andstæðing þá byrjar Unnar. Hann dregur þá skaðagildi sitt frá fjölda heilsustiga andstæðings. Svo gerir andstæðingurinn slíkt hið sama og skiptast þeir á þar til annar hefur $0$ eða færri heilsustig. Þá tapar sá einstaklingur. Ef Unnar tapar getur hann ekki komist úr hellunum, en ef hann sigrar getur hann farið í annað herbergi en heilsustig hans haldast óbreytt frá því úr bardaganum.

Hellakerfið er mjög mishæðótt svo það er ekki hægt að ferðast allar leiðir í báðar áttir. Tákna má hellakerfið með $n$ svæðum og $m$ einstefndra gönguleiða milli svæðanna þar sem Unnar byrjar á svæði $1$ og vill komast í svæði $n$. Á hverri gönguleið er einn andstæðingur en svæðin eru laus andstæðinga.

Inntak

Fyrsta línan inniheldur heiltölur $A, H$ þ.a. $1 \leq A, H \leq 10^9$ þar sem $A$ er skaðagildi Unnars og $H$ er upphaflegur fjöldi heilsustiga hans. Næst kemur lína með tveimur heiltölum $n, m$ þ.a. $1 \leq n, m \leq 10^5$ þar sem $n$ er fjöldi svæða og $m$ er fjöldi göngustíga. Næst fylgja $m$ línur með 4 heiltölum $e_ i, b_ i, a_ i, h_ i$ þ.a. $1 \leq e_ i, b_ i \leq n$ og $1 \leq a_ i, h_ i \leq 10^9$. Þetta segir þá að til sé göngustígur frá svæði $e_ i$ að svæði $b_ i$ og á honum sé andstæðingur með skaðagildi $a_ i$ og $h_ i$ heilsustig.

Úttak

Ef engin leið er fyrir Unnar að komast að endapunktinum, prentið ‘Oh no’ án gæsalappanna. Annars prentið þið eina heiltölu $h$, hámarksfjölda heilsustiga sem Unnar getur verið með þegar hann er kominn í svæði $n$.

1 2
3 2
1 2 1 2
2 3 1 2

Oh no

1 3
3 2
1 2 1 2
2 3 1 2

1

5 20
5 6
1 2 10 6
1 3 2 15
1 4 1 33
2 5 1 7
3 4 1000 5
4 2 5 9

10