Ádám és Éva kétszemélyes játékot játszik egy N mezőt tartalmazó játéktáblán. A játék során
az első mezőről indulva, felváltva lépve, egy bábut mozgatnak a játéktáblán, ugyanarra a
mezőre többször is léphetnek. Egy adott mezőről csak szomszédos mezőre lehet lépni egy lépésben. Minden mezőre rá van írva egy pontszám. Ádám kezdi a játékot. Ha Ádám az aktuális
lépésében az m mezőre lép, amire p pontszám van írva, akkor összpontszáma p értékkel növelődik.
Ha Éva az m mezőre lép, amire p pontszám van írva, akkor Ádám összpontszámát
csökkentik p értékkel. Ádám célja, hogy a lehető legtöbb összpontot szerezze, Éva célja pedig
az, hogy Ádám a lehető legkevesebb összpontot szerezzen a játék során. Az összpontszám lehet
negatív is, ekkor Ádám fizet Évának a játék végén.
Feladat
Készíts programot, amely kiszámítja, hogy mekkora az a legnagyobb összpontszám, amit Ádám biztosan meg tud szerezni K lépéses játékban, bárhogyan is lép Éva!
Bemenet
A jatek.be szöveges állomány első sorában két egész szám van egy szóközzel elválasztva, a játéktáblán lévő mezők N száma (1≤N≤500) és a játékban megteendő lépések K száma (1≤K≤2000). (Tehát mindkét játékos K lépést tesz felváltva.) A második sor pontosan N pozitív egész számot tartalmaz egy-egy szóközzel elválasztva, az m-edik szám az m sorszámú mezőn lévő pontszám értéke, legfeljebb 1000. A következő N sor írja le a mezők szomszédjait, tehát, hogy adott mezőről mely mezőkre lehet lépni közvetlenül. Az állomány m+2-edik sora az m-edik mező szomszédjait tartalmazza egy-egy szóközzel elválasztva, 0-val zárva. Minden mezőről legalább egy másik mezőre lehet lépni. Minden mezőnek önmaga is lehet szomszédja.
Kimenet
A jatek.ki szöveges állomány első és egyetlen sorába egy egész számot kell írni, a legnagyobb összpontszámot, amit Ádám meg tud szerezni K lépéses játékban, bárhogyan is lép Éva!
Példa
Bemenet |
Kimenet |
5 2 2 5 8 9 3 3 2 0 4 1 0 2 5 0 3 2 0 4 2 1 0 | 4
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2013, 11-13. évfolyam, döntő
Algoritmusok: dinamikus programozás