Условие

---

CODE@BURGAS 2026, ГРУПА A, ЗАДАЧА D. РАНИЦА С КОНФЛИКТИ И БОНУСИ
---
Имате раница с максимална вместимост W килограма и N предмета, всеки от които има тегло и стойност. За всеки предмет са дадени тегло w[i] и стойност v[i]. Задачата е да изберете подмножество от предметите така че: 
1.	Общото тегло да не превишава W. 
2.	Да бъдат избрани най-много T предмета. 

Ограничения: 
- Има K двойки конфликти. Ако предмет A е в конфликт с предмет B, те не могат да се вземат заедно. 
- Има M бонус групи. Ако се изберат всички предмети от дадена група, се добавя допълнителна стойност. 

Вход: 
Първият ред от стандартния вход съдържа три цели числа: W — максимална вместимост на раницата (в килограми); N — брой на предметите; T — максимален брой предмети, които могат да бъдат избрани.
Следват N реда, всеки съдържащ по две цели числа: w[i] — тегло на i-тия предмет и v[i] — стойност на i-тия предм. 
Следва едно цяло число K — брой на конфликтните двойки.
Следват K реда, всеки със следните две цели числа: a, b — индекси на два предмета (1 ≤ a, b ≤ N), които са в конфликт. Това означава, че предметите a и b не могат да бъдат избрани едновременно.
Следва едно цяло число M — брой на бонус групите.
Следват M реда, всеки със следния формат:
- първо число k - брой на предметите в групата
- следват k цели числа - индекси на предмети (1 ≤ индекс ≤ N)
- последно число bonus - допълнителна стойност

Изход: 
На един ред на стандартния изход програмата трябва да изведе максималната възможна стойност. 

Примерен вход:
50 5 3
10 60
20 100
30 120
15 70
25 90
2
1 2
3 4
2
2 2 3 50
3 1 4 5 100	

Примерен изход:
320