Gaming
НОИ 2009, Контролно 2
Time Limit: 1s, Memory Limit: 64MiB
Юни месец е, дните са дълги, нощите топли и ароматни. Като всяка друга млада влюбена двойка, Ели и приятелят й прекарват часове наред заедно попаднали в обятията на... компютърните игри. Превъртяли WоW, стигнали 100-тен левел на Diablo и изиграли всяка random карта на Heroes, сега те са се захванали с малко по-нестандартна игра.

В нев всяко ниво може да се представи като неориентиран граф, всеки връх на който е оцветен в бяло или черно. Имаме дефинирана следната операция „смяна на съюза”: при използването й върху даден (да кажем черен) връх, цветът на всички върхове, които могат да се достигнат, използвайки като междинни единствено върхове със същия цвят (за примера – черен) сменят цвета си. Ето графична илюстрация какво става ако използваме операцията върху върха с Х.
Graph Before Graph After
Целта на играта за всяко ниво е да се направят всички върхове бели или черни (в зависимост от нивото). Очевидно това винаги е възможно; за съжаление смяната на съюза на група върхове отнема известно време (на по-сложните нива отнема повече време). Например ако за горния граф смяната на съюза отнема 14 единици време и искаме да направим целия граф бял, то за цялото ниво ще са нужни 3 * 14 = 42 единици време (забележете, че оптималната игра представлява използване на операцията два последователни пъти върху бял в началото връх (да кажем единствения с едно ребро) и после използване на операцията в/у изолирания черен връх).

Елеонора и приятелят й играят едновременно, като могат да си поделят нивата по произволен начин (и двамата са еднакво добри), но не могат да играят едновременно едно и също ниво. Не е задължително да са минали по-просто ниво за да играят по-сложно.

От вас се иска да намерите минималното време, за което двамата могат да превъртят играта (да минат всички нива).
Вход
На първия ред на стандартния вход е зададен броят нива L на играта. На следващите няколко реда е описано първото ниво, после второто и така нататък. Всяко ниво започва с ред, съдържащ целите числа Ni, Mi, Ci и Ti – съответно броя върхове в i-тото ниво, броя ребра в графа, цвета, в който трябва да бъде оцветен целия граф за да се мине нивото (0 за бяло и 1 за черно) и времето, което отнема всяка операция. Следват Ni на брой числа (0 или 1) задаващи първоначалните цветове на всеки връх. След тях са зададени Mi двойки числа (Xij, Yij), съответстващи на неориентирано ребро между върхове с индекси Xij и Yij. С това описанието на i-тото ниво завършва и започва описанието на следващото, ако има такова.
Изход
На стандартния изход изведете минималното време, необходимо за превъртането на играта (напомняме, че за да е мината играта, трябва всяко ниво да е завършено от поне един от двамата).
Ограничения
  • 1 ≤ L ≤ 40
  • 1 ≤ Ni ≤ 100
  • 0 ≤ Мi ≤ 10,000
  • 0 ≤ Ci ≤ 1
  • 0 ≤ Ti ≤ 1,000,000
  • 1 ≤ Xij, YijNi
Примерен Вход Примерен Изход
3 3 2 0 9 0 1 0 1 2 2 3 7 7 0 5 1 1 0 0 1 0 1 3 1 2 3 1 4 3 4 4 5 5 6 7 6 2 1 1 7 1 0 1 2 16
Първо и трето ниво могат да се минат с по един ход (на първо - като сменим цвета на връх 2 от черен на бял; на трето - на връх 2 от бял на черен), докато второ може да се мине с най-малко 3 хода (като сменим цвета на връх 3 от бял на черен, после от черен на бял (съответно правим всички върхове без 7 бели), и с третия си ход сменим цвета на 7 от черен на бял). Така времената, необходими за трите нива, са съответно 9, 15 и 7.
Оптимално разпределение на нивата е първо и трето за единия, второ за другия, като отговорът на задачата е max(9 + 7, 15) = 16.
Мрън!