Mall
Национална Олимпиада по Информатика 2009, Контролно 3
Time Limit: 0.3s, Memory Limit: 64MiB
Най-хубавото нещо на учебния ден е, че свършва. Чак след този преломен момент на денонощието Ели влиза във вихъра си – по пътя от училище до тях тя успява да посети хиляди места, като МакДоналдс, Мола, киното, фризьорския салон, и още какво ли не. Тъй като високите токчета пречат особено на дългите разходки, ако Ели избере да отиде в даден регион на града, е възможно тя да не може да отиде в други негови части (примерно ако реши да ходи до Мола, то това изключва разходка по Витошка – твърде далеч е).

Като цяло следучилищната обиколка на града е една нелесна за решаване задача. За това Ели определя за всеки обект на интерес някаква "печалба" ако отиде там. Логично, ако веднъж тя е влязла в даден магазин, следващите ѝ посещения не ѝ носят удовлетворение, но пък това не ѝ пречи да минава по няколко пъти от там, ако иска да стигне до някъде другаде.

Градът може да се представи като насочен граф с N върха - местата, където тя иска да отиде. Всеки връх има дадена "печалба" Ai при първо посещение. Възможно е някои върхове да не са достижими от други. Имайки предвид, че Ели тръгва от връх 1 (училището), и иска да достигне връх N (нейния дом), можете ли да ѝ помогнете да определи каква е максималната печалба, която може да събере ако избере оптимален маршрут? Връх N може да бъде посетен повече от веднъж, но обиколката трябва да завърши там.
Вход
На първия ред на стандартния вход са зададени целите числа N и М – броят върхове и ребра в графа. На следващия ред има N числа A1, A2, ..., AN – определената печалба за всеки връх. Следват M реда, всеки съдържащ двойка цели числа Xi Yi, указващи насочено ребро от Xi към Yi.
Изход
На стандартния изход изведете максималната стойност, която Ели може да събере по пътя. Ако не съществува път между началния и крайния връх, отпечатайте -1.
Ограничения
  • 2 ≤ N ≤ 100,000
  • 1 ≤ M ≤ 200,000
  • 0 ≤ Ai ≤ 1,000,000
  • 1 ≤ Xi, YiN
Примерен Вход Примерен Изход
6 7 12 11 2 7 8 13 1 2 2 6 1 3 3 6 3 4 4 5 5 3 42
Оптималният път е 0 -> 2 -> 3 -> 4 -> 2 -> 5, даващ сума 12 + 2 + 7 + 8 + 0 +13 = 42.
Мрън!