Փոշեկուլ

Ջեֆը ունի մեծ տուն, որը բաղկացած է սենյակից՝ միացված միջանցքով։ Յուրաքանչյուր միջանցք միացնում է երկու տարբեր սենյակ, և բոլոր սենյակները միմյանց հետ կապված են։ Յուրաքանչյուր միջանցքի երկարությունը 1 մետր է։ Ջեֆը հաճախ մաքրում է բնակարանի սենյակները, բայց հազվադեպ՝ միջանցքները։ Միջանցքներում փոշի է կուտակվել, և հիմա Ջեֆը ուզում է դրանք փոշեկուլել։

Յուրաքանչյուր փոշեկուլ, ցավոք, ունի նաև սահմանափակ երկարության լար։ Յուրաքանչյուր սենյակում կա վարդակ, և փոշեկուլը պետք է միացված լինի որևէ սենյակի վարդակին, որպեսզի աշխատի։ Ջեֆը սկսում է 1-ին սենյակից և կարող է անել հետևյալը․

Եթե փոշեկուլը միացված չէ հոսանքին (և նա գտնվում է փոշեկուլի հետ նույն սենյակում), նա կարող է․

• Միացնել այն (խրոցը մտցնել) այն սենյակում, որտեղ գտնվում է։

• Վերցնել փոշեկուլը ձեռքը և անցնել հարևան սենյակներից մեկը։ Միջանցքով անցնելու համար պետք է 1 րոպե։

Եթե փոշեկուլը միացված է հոսանքին (և նա գտնվում է փոշեկուլի հետ նույն սենյակում), նա կարող է․

• Եթե գտնվում է այն սենյակում, որտեղ միացրել է փոշեկուլը, կարող է անջատել այն վարդակից։

• Անցնել հարևան սենյակներից մեկը՝ ճանապարհին փոշեկուլելով միջանցքը։ Սա կարող է անել միայն այն դեպքում, եթե լարը բավարար երկար է։ Այսինքն՝ եթե այն սենյակից, որտեղ փոշեկուլը միացված է, մինչև նպատակային սենյակ հեռավորությունը փոքր կամ հավասար է լարի երկարությանը։ Միջանցքը մաքրելու համար պետք է 1 րոպե։

Ջեֆի փոշեկուլը փչացել է։ Հիմա նա գտնվում է մի խանութում, որտեղ կա փոշեկուլ, և դրանցից -րդի լարի երկարությունը մետր է։ Նրան հետաքրքրում է՝ յուրաքանչյուր փոշեկուլի համար նվազագույնը որքան ժամանակ կպահանջվի բոլոր միջանցքները փոշեկուլելու համար, եթե գնի տվյալ փոշեկուլը։ Օգնեք նրան որոշել այդ ժամանակները։

Մուտքային տվյալները

Առաջին տողում տրված են երկու բնական թիվ՝ և ․ սենյակների և փոշեկուլների քանակները։

Հաջորդ տողերում տրված են և () բնական թվերը, որոնք նշանակում են, որ գոյություն ունի միջանցք սենյակների և միջև։

Վերջին տողում տրված են թվեր՝ (). փոշեկուլների լարերի երկարությունները։

Ելքային տվյալները

Միակ տողում արտածեք թիվ, որտեղ -րդ թիվը ներկայացնում է նվազագույն ժամանակը -րդ փոշեկուլով մաքրելու համար։

Օրինակներ

5 2
1 2
2 3
3 4
4 5
2 5

8 4

10 2
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
1 3

24 16

6 2
3 1
3 5
4 3
4 2
2 6
5 1

6 12

Ենթախնդիրներ

Բոլոր ենթախնդիրներում գործում է՝ և ։