Gravitony

Po dlouhých neúspěšných pokusech byly konečně detekovány elementární částice gravitačního pole – gravitony – a začala jejich měření. Ukázaly se nové a dosud nepředpokládané vlastnosti těchto částic.
Graviton se může nacházet v různých energetických hladinách. V každé z možných energetických hladin má graviton spin buď 0 nebo 1, a pro každou hladinu je tato hodnota fixní a nemůže se měnit. V podmínkách měření graviton nikdy nepřechází na hladinu s vyšší energií a při přechodu na hladinu s nižší energií vyzáří vždy určitý počet světelných kvant. Graviton také nemůže přejít na zcela libovolnou hladinu s nižší energií, ke každé hladině existuje jen několik hladin s nižší energií, do kterých může přejít.
Měřící aparatura dosud není dokonalá a vykazuje systematické poruchy, pokud měří přechod gravitonu z energetické hladiny se spinem 1 do energetické hladiny se spinem 0.

Je zapotřebí navrhnout experiment, v němž bude sledován jeden graviton. Na začátku experimentu bude graviton v energetické hladině se spinem 0 a na konci bude v energetické hladině se spinem 1. Pro kalibraci detektorů je nutno znát maximální celkový počet kvant, která graviton může vyzářit při postupném sestupování na nižší energetické hladiny, a to za předpokladu, že graviton nezpůsobí poruchu aparatury.
Jednotlivé energetické hladiny jsou označeny čísly v pořadí jejich objevování, nikoli postupně podle výše energie. Taková neshoda je v přírodních vědách běžná a experimentátoři se s ní musí vypořádat.

     

Obrázek 1. Schémata všech možných sestupů gravitonu na hladinu s nižší energií. Jednotlivé hladiny jsou znázorněny jako uzly, šipky určují směr přechodu na hladinu s nižší energií. U každého přechodu je uveden jemu příslušný počet vyzářených kvant. Hladiny se spinem 0 jsou znázorněny jako světlé uzly, hladiny se spinem 1 jsou znázorněny jako tmavé uzly. Varianty a), b) a c) odpovídají Příkladům 1, 2 a 3 níže. Maximální možné bezporuchově naměřené počty vyzářených kvant v jednotlivých variantách jsou: a) 50, b) 22, c) 110. Je jich možno dosáhnout posloupností přechodů: a) 0 − 2 − 5, b) 2 − 4 − 5 − 3 − 0, c) 0 − 6 − 7 − 5 − 4 − 2.

Úloha

Je dán spin gravitonu v každé energetické hladině a počty vyzářených kvant při všech možných přechodech z hladiny s určitou energií gravitonu na hladinu s nižší energií gravitonu. Určete maximální celkový počet kvant, která graviton může vyzářit během navrhovaného experimentu při postupném sestupování na nižší energetické hladiny, za předpokladu, že graviton nezpůsobí poruchu aparatury.

Vstup

První řádek obsahuje dvě celá čísla N, M, oddělená mezerou a představující (v tomto pořadí) počet energetických hladin a počet přechodů mezi nimi. Hladiny jsou očíslovány celými čísly 0, 1, ..., N − 1. Na druhém řádku je ve vzrůstajícím pořadí čísel hladin uveden spin gravitonu příslušející dané hladině. Hodnoty spinů jsou odděleny mezerami. Následuje M řádků, každý specifikuje jeden přechod gravitonu do nižší energetické hladiny. Řádek obsahuje tři celá čísla A, B, K (v tomto pořadí) oddělená mezerou. Graviton přechází z hladiny A do hladiny B a vyzáří přitom K světelných kvant.
Platí: 2 ≤ N ≤ 104, 2 ≤ M ≤ 106, v každém přechodu graviton vyzáří nejvýše 1000 světelných kvant.

Výstup

Výstup obsahuje jeden textový řádek s jedním celým číslem udávajícím maximální počet kvant, která graviton může vyzářit za podmínek specifikovaných v úloze.

Příklad 1

Vstup
6 7
0 0 0 1 1 1
0 2 10
0 3 20
1 5 30
1 3 12
1 4 45
2 5 40
3 5 19
Výstup
50
Schéma možných přechodů gravitonu do různých energetických hladin v Příkladu 1 je znázorněno na Obrázku 1a).

Příklad 2

Vstup
8 13
1 1 0 0 0 0 1 1
2 1 9
1 7 5
7 6 4
6 0 3
2 4 5
4 5 6
5 3 7
3 0 4
1 4 1
4 7 4
7 5 1
5 6 4
6 3 1
Výstup
22
Schéma možných přechodů gravitonu do různých energetických hladin v Příkladu 2 je znázorněno na Obrázku 1b).

Příklad 3

Vstup
8 12
0 1 1 0 1 1 0 0
0 1 10
3 2 10
5 4 10
6 7 30
0 6 20
4 2 30
5 3 20
1 7 20
0 2 30
1 3 10
6 4 30
7 5 20
Výstup
110
Schéma možných přechodů gravitonu do různých energetických hladin v Příkladu 3 je znázorněno na Obrázku 1c).

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data