Беси открыла агентство путешествий вдоль реки Амазонка. Имеется несколько туристических мест на обоих сторонах реки, для каждого некоторое целое число задает насколько это место интересно туристам.
Туристические места соединены маршрутами через реку. Иными словами, нет маршрутов, соединяющих туристические места по одной стороне реки.
Беси хочет найти такую последовательность посещения туристических мест чтобы максимизировать сумму значений ассоциированных с каждым посещенным местом и чтобы никакие два маршрута в этой последовательности не пересекались.
Два маршрута (a <-> x) и (b <-> y) пересекаются тогда и только тогда, когда (a < b и y < x) или ((b < a и x < y) или (a = b and x = y).
Помогите Беси найти такой маршрут. Беси может начинать и заканчивать маршрут в любом месте и на любой стороне реки. PROBLEM NAME: route
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа N (1 <= N <= 40,000), M (1 <=M <= 40,000), и R (0 <= R <= 100,000) указывающих соответственно количество мест на левой стороне реки, количество мест на правой стороне реки и количество маршрутов.
* Строки 2..N+1: (i+1)-ая строка содержит одно целое число, Li (0 <= Li <= 40,000), указывающее число i-го места на левой стороне реки
* Строки N+2..N+M+1: (i+N+1)-ая строка содержит одно целое число, Ri (0 <= Ri <= 40,000), указывающее число i-го места на правой стороне реки
* Строки N+M+2..N+M+R+1: Каждая строка содержит два целых числа разделенных пробелом I (1 <= I <= N) и J (1 <= J <= M) указывающих двунаправленный маршрут между местом I на левой стороне реки и местом J на правой стороне реки.
Формат выходных данных
* Строка 1: Одно целое число, указывающее максимальную сумму значений включенных в тур.
Примечание
Оптимальный тур начинается в месте 1 на левой стороне, затем в место 1 на правой стороне и затем сайт 3 слева. Соответсвующие значения 1 2 5 дают сумму 8.