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.