Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Париз је познат по бројним атракцијама и знаменитостима које се могу видети у том граду. У последњој предизборној кампањи, градски оци Париза су изградили нове, лепе и модерне, пешачке путеве између атракција. Како би даље финансирали своју кампању, смислили су и начин како могу преварити несмотрене грађане и туристе - пешачке путеве су направили једносмерним, и свакоме ко се креће у супротном смеру биће написана казна. За сваку атракцију у граду, направљен је тачно један пешачки пут који води до ње.
Ана ће ове године први пут ићи у Париз, и са свиме овиме је добро упозната. Она јако жели да испланира свој обилазак и да уопште не губи време тамо. На интернету је истражила апсолутно све атракције, и свакој је доделила оцену колико јој се свиђа. Ипак, пошто атракција има много, а Ана мора и да спакује ствари, моли вас да јој помогнете у планирању обиласка.
Ана вам даје нову мапу Париза где су уписани сви пешачки путеви, од које до које атракције воде, и колико времена траје пешачење тим путем. Такође ће вам дати своје оцене атракција, и укупно време које ће провести у Паризу. Ваш задатак је да јој кажете колика је највећа укупна лепота атракција које она може да обиђе (укупна лепота је сума оцена сваке атракције коју обиђе), тако да се Ана креће само новим пешачким путевима. Ана свој обилазак може почети од било које атракције.
Имајте у виду да Ана када обилази атракције не губи ни мало времена разгледајући, њој је довољно само да се слика за Инстаграм и да иде даље. Управо зато, могуће је да неке атракције обиђе и по више пута, а да су јој и даље исто лепе као што су јој биле и на почетку (односно, уколико више пута обиђе исту атракцију, сваки пут ће се њена оцена додати на укупну лепоту пута).
У првој линији се налазе два природна броја \(N\) и \(T\) - број атракција, и време које ће Ана провести у Паризу. У другој линији се налази \(N\) природних бројева - оцене које је Ана дала атракцијама. У трећој линији се налази \(N\) природних бројева - низ \(X_i\). У четвртој линији се налази \(N\) природних бројева - низ \(D_i\). Низови \(X\) и \(D\) описују једносмерне пешачке путеве - пут који води до атракције \(i\) почиње од атракције \(X_i\), и потребно је \(D_i\) времена да се препешачи. Атракције су индексиране бројевима од \(1\) до \(N\).
У први и једини ред излаза исписати један број - највећу укупну лепоту атракција које Ана може да обиђе.
5 7
7 3 1 4 8
4 3 5 2 1
3 2 4 1 716У овом примеру постоји \(5\) атракција, а пешачки путеви који постоје су \(4 \rightarrow 1\) дужине \(3\), \(3 \rightarrow 2\) дужине \(2\), \(5 \rightarrow 3\) дужине \(4\), \(2 \rightarrow 4\) дужине \(1\) и \(1 \rightarrow 5\) дужине \(7\). Време којие ће Ана провести у Паризу је \(7\), и за то време највећа укупна лепота атракција које може да обиђе је \(16\) ако иде путем: \(5 \rightarrow 3 \rightarrow 2 \rightarrow 4\).
6 200
1 1 1 1 1 100
3 1 2 5 4 5
1 1 1 10 10 1201Да би овде постигла највећу лепоту, Ана ће се вртети у круг између пар атракција. Једна могућност је да крене од \(2\), а пут би био \(2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow \ldots \rightarrow 1\)
Постоје четири подзадатка: