Power Network
Енергетична мережа складається з вузлів (електростанцій, споживачів та диспетчерів), з'єднаних лініями передачі електроенергії. Вузол u може мати запас s(u) ≥ 0 електроенергії, виробляти від 0 до p_max(u) електроенергії, споживати від 0 до min(s(u),c_max(u)) електроенергії, і передавати d(u)=s(u)+p(u)-c(u) електроенергії. Діють такі обмеження: c(u)=0 для електростанцій, p(u)=0 для споживачів, і p(u)=c(u)=0 для диспетчерів. У мережі може бути не більше однієї лінії передачі (u,v) від вузла u до вузла v, яка передає від 0 до l_max(u,v) електроенергії. Нехай Con = _u(cu) - це загальна спожита електроенергія в мережі. Завдання полягає в обчисленні максимального значення Con.
На рисунку наведено приклад. Позначка x/y для електростанції u означає, що p(u)=x і p_max(u)=y. Для споживача u позначка x/y означає, що c(u)=x і c_max(u)=y. Для лінії передачі (u,v) позначка x/y означає, що l(u,v)=x і l_max(u,v)=y. Спожита електроенергія становить Con=6. Зверніть увагу, що існують інші можливі стани мережі, але значення Con не може перевищувати 6.
Вхідні дані
Вхідний файл містить кілька наборів даних, кожен з яких описує енергетичну мережу. Кожен набір починається з чотирьох цілих чисел: 0 ≤ n ≤ 100 (кількість вузлів), 0 ≤ n_p ≤ n (кількість електростанцій), 0 ≤ n_c ≤ n (кількість споживачів), і 0 ≤ m ≤ n^2 (кількість ліній передачі). Далі йдуть m трійок (u,v)z, де u і v - ідентифікатори вузлів (починаючи з 0) і 0 ≤ z ≤ 1000 - значення l_max(u,v). Потім йдуть n_p дуплетів (u)z, де u - ідентифікатор електростанції і 0 ≤ z ≤ 10000 - значення p_max(u). Набір даних завершується n_c дуплетами (u)z, де u - ідентифікатор споживача і 0 ≤ z ≤ 10000 - значення c_max(u). Усі вхідні числа є цілими. Окрім трійок (u,v)z і дуплетів (u)z, які не містять пробілів, пробіли можуть вільно зустрічатися у вхідних даних. Вхідні дані завершуються кінцем файлу і є коректними.
Вихідні дані
Для кожного набору даних програма повинна вивести на стандартний вихід максимальну кількість електроенергії, яку можна спожити у відповідній мережі. Кожен результат має бути цілим числом і виводитися з початку окремого рядка.