Юни месец е, дните са дълги, нощите топли и ароматни. Като всяка друга млада влюбена двойка, Ели и приятелят й прекарват часове наред заедно попаднали в обятията на... компютърните игри. Превъртяли WоW, стигнали 100-тен левел на Diablo и изиграли всяка random карта на Heroes, сега те са се захванали с малко по-нестандартна игра.

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

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

От вас се иска да намерите минималното време, за което двамата могат да превъртят играта (да минат всички нива). На първия ред на стандартния вход е зададен броят нива L на играта. На следващите няколко реда е описано първото ниво, после второто и така нататък. Всяко ниво започва с ред, съдържащ целите числа N_i, M_i, C_i и T_i – съответно броя върхове в i-тото ниво, броя ребра в графа, цвета, в който трябва да бъде оцветен целия граф за да се мине нивото (0 за бяло и 1 за черно) и времето, което отнема всяка операция. Следват N_i на брой числа (0 или 1) задаващи първоначалните цветове на всеки връх. След тях са зададени M_i двойки числа (X_ij, Y_ij), съответстващи на неориентирано ребро между върхове с индекси X_ij и Y_ij. С това описанието на i-тото ниво завършва и започва описанието на следващото, ако има такова. На стандартния изход изведете минималното време, необходимо за превъртането на играта (напомняме, че за да е мината играта, трябва всяко ниво да е завършено от поне един от двамата).

• 1 ≤ L ≤ 40
• 1 ≤ N_i ≤ 100
• 0 ≤ М_i ≤ 10,000
• 0 ≤ C_i ≤ 1
• 0 ≤ T_i ≤ 1,000,000
• 1 ≤ X_ij, Y_ij ≤ N_i

Примерен Вход	Примерен Изход
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