Велике чаювання
Обмеження: 2 сек., 256 МіБ
Іноді Лесику, Роману та Віталіку стає нудно пити чай самим. Тоді вони влаштовують невеличкі вечірки шанувальників чаю.
У хлопців є \(t\) друзів, яких вони можуть запросити на вечірку. Для \(i\)-го свого друга вони знають два числа: \(a_i\) — скільки літрів чаю він приносить з собою на вечірку, та \(b_i\) — скільки літрів чаю він випиває за вечірку. Деякі з друзів Лесика, Романа та Віталіка товаришують між собою більше ніж з іншими, а тому ходять на вечірки тільки разом. Тому, якщо на вечірку запросити одного з таких друзів, то обов’язково прийде і другий. Очевидно, що наші герої хочуть, щоб різниця між сумарною кількістю літрів чаю, який принесуть гості, та кількістю літрів чаю, який ті вип’ють, була якомога більшою, адже все, що залишиться, хлопці зможуть випити самі.
Допоможіть хлопцям визначити, яку найбільшу кількість літрів чаю вони зможуть випити самі.
Вхідні дані
У першому рядку два цілі числа: \(n\) — кількість друзів Лесика, Віталіка та Романа, та \(m\) — кількість пар друзів, що ходять на вечірки тільки разом.
У наступних \(n\) рядках по два числа: \(a_i\) та \(b_i\).
В наступних \(m\) рядках по два числа: \(x_i\) та \(y_i\) — порядкові номери друзів, які відвідують вечірки разом.
Вихідні дані
Єдине число — максимальна кількість літрів чаю, що принесуть і не вип’ють гості.
Обмеження
\(1 \le n \le 100\),
\(1 \le m \le 10^4\),
\(0 \le a_i, b_i \le 10^3\),
\(1 \le x_i, y_i \le n\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 1 10 3 2 10 7 6 1 2 | 1 |
Примітки
Вигідно запросити лише третього друга, адже якщо запросити ще першого, то прийде і другий.
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|