Pariz je poznat po brojnim atrakcijama i znamenitostima koje se mogu videti u tom gradu. U poslednjoj predizbornoj kampanji, gradski oci Pariza su izgradili nove, lepe i moderne, pešačke puteve između atrakcija. Kako bi dalje finansirali svoju kampanju, smislili su i način kako mogu prevariti nesmotrene građane i turiste - __pešačke puteve su napravili jednosmernim__, i svakome ko se kreće u suprotnom smeru biće napisana kazna. Za svaku atrakciju u gradu, napravljen je __tačno jedan pešački put koji vodi do nje__.

Ana će ove godine prvi put ići u Pariz, i sa svime ovime je dobro upoznata. Ona jako želi da isplanira svoj obilazak i da uopšte ne gubi vreme tamo. Na internetu je istražila apsolutno sve atrakcije, i svakoj je dodelila ocenu koliko joj se sviđa. Ipak, pošto atrakcija ima mnogo, a Ana mora i da spakuje stvari, moli vas da joj pomognete u planiranju obilaska.

Ana vam daje novu mapu Pariza gde su upisani svi pešački putevi, od koje do koje atrakcije vode, i koliko vremena traje pešačenje tim putem. Takođe će vam dati svoje ocene atrakcija, i ukupno vreme koje će provesti u Parizu. Vaš zadatak je da joj kažete __kolika je najveća ukupna lepota atrakcija koje ona može da obiđe__ (ukupna lepota je suma ocena svake atrakcije koju obiđe), tako da se Ana kreće samo novim pešačkim putevima. Ana svoj obilazak može početi od bilo koje atrakcije.

Imajte u vidu da Ana kada obilazi atrakcije ne gubi ni malo vremena razgledajući, njoj je dovoljno samo da se slika za Instagram i da ide dalje. Upravo zato, moguće je da neke atrakcije obiđe i po više puta, a da su joj i dalje isto lepe kao što su joj bile i na početku (odnosno, ukoliko više puta obiđe istu atrakciju, svaki put će se njena ocena dodati na ukupnu lepotu puta).

Opis ulaza

U prvoj liniji se nalaze dva prirodna broja ~N~ i ~T~ - broj atrakcija, i vreme koje će Ana provesti u Parizu. U drugoj liniji se nalazi ~N~ prirodnih brojeva - ocene koje je Ana dala atrakcijama. U trećoj liniji se nalazi ~N~ prirodnih brojeva - niz ~X_i~. U četvrtoj liniji se nalazi ~N~ prirodnih brojeva - niz ~D_i~. Nizovi ~X~ i ~D~ opisuju jednosmerne pešačke puteve - put koji vodi do atrakcije ~i~ počinje od atrakcije ~X_i~, i potrebno je ~D_i~ vremena da se prepešači. Atrakcije su indeksirane brojevima od ~1~ do ~N~.

Opis izlaza

U prvi i jedini red izlaza ispisati jedan broj - najveću ukupnu lepotu atrakcija koje Ana može da obiđe.

Primer 1

Ulaz

5 7
7 3 1 4 8
4 3 5 2 1
3 2 4 1 7

Izlaz

16

Objašnjenje primera

U ovom primeru postoji \(5​\) atrakcija, a pešački putevi koji postoje su \(4 \rightarrow 1​\) dužine \(3​\), \(3 \rightarrow 2​\) dužine \(2​\), \(5 \rightarrow 3​\) dužine \(4​\), \(2 \rightarrow 4​\) dužine \(1​\) i \(1 \rightarrow 5​\) dužine \(7​\). Vreme kojie će Ana provesti u Parizu je \(7​\), i za to vreme najveća ukupna lepota atrakcija koje može da obiđe je \(16​\) ako ide putem: \(5 \rightarrow 3 \rightarrow 2 \rightarrow 4​\).

Primer 2

Ulaz

6 200
1 1 1 1 1 100
3 1 2 5 4 5
1 1 1 10 10 1

Izlaz

201

Objašnjenje primera

Da bi ovde postigla najveću lepotu, Ana će se vrteti u krug između par atrakcija. Jedna mogućnost je da krene od ~2~, a put bi bio ~2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow \ldots \rightarrow 1~

Ograničenja

• ~2 \leq N \leq 10^5~
• ~1 \leq T \leq 10^{12}~
• ~1 \leq A_i \leq 10^6~
• ~1 \leq D_i \leq 10^6~

Postoje četiri podzadatka:

• Podzadatak 1 [22 poena]: \(N, T \leq 1000​\).
• Podzadatak 2 [17 poena]: ~N \leq 1000~, i ~T \leq 10^{12}~.
• Podzadatak 3 [14 poena]: ~D_i = 1~ za svako ~i~, odnosno vreme potrebno da se svaki put prepešači je ~1~.
• Podzadatak 4 [23 poena]: Niz ~X~ je permutacija brojeva od ~1~ do ~N~, odnosno iz svake atrakcije kreće tačno jedan put.
• Podzadatak 5 [24 poena]: Nema dodatnih ograničenja.