| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 512 MB | 65 | 11 | 8 | 15.686% |
Победитель студенческой олимпиады получил предложения о стажировке от двух университетов. При подготовке планов обучения он узнал рейтинг качества преподавания каждой дисциплины в этих университетах.
Программа обучения первого университета состоит из последовательности перечисленных в хронологическом порядке $n$ различных дисциплин $a_1, a_2, \ldots, a_n,ドル имеющих рейтинги $x_1, x_2, \ldots, x_n$ соответственно. Программа обучения второго университета состоит из последовательности перечисленных в хронологическом порядке $m$ различных дисциплин $b_1, b_2, \ldots, b_m,ドル имеющих рейтинги $y_1, y_2, \ldots, y_m$ соответственно.
Студент имеет возможность составить план обучения в первом университете таким образом, чтобы изучить дисциплины на позициях учебной программы с $l_a$ по $r_a$ включительно (1ドル \leq l_a \leq r_a \leq n$), либо отказаться от стажировки в первом университете. Аналогично он может составить план обучения во втором университете таким образом, чтобы изучить дисциплины на позициях учебной программы с $l_b$ по $r_b$ включительно (1ドル \leq l_b \leq r_b \leq m$), либо отказаться от стажировки во втором университете.
Изучать одну и ту же дисциплину дважды в разных университетах не имеет смысла, поэтому все дисциплины в двух выбранных планах обучения должны быть различны.
Требуется написать программу, которая определит планы обучения студента таким образом, чтобы получить наибольшую возможную сумму рейтингов изучаемых дисциплин.
Первая строка входных данных содержит целые числа $n$ и $m$ --- количество дисциплин в программах обучения первого и второго университетов (1ドル \leq n, m \leq 500,000円$).
Вторая строка входных данных содержит $n$ целых чисел $a_i$ --- дисциплины, входящие в программу обучения первого университета, перечисленные в хронологическом порядке (1ドル \leq a_i \leq n + m$).
Третья строка входных данных содержит $n$ целых чисел $x_i$ --- рейтинги дисциплин, входящих в программу обучения первого университета, перечисленные том же порядке, что и дисциплины $a_i$ (1ドル \leq x_i \leq 10^9$).
Четвёртая строка входных данных содержит $m$ целых чисел $b_i$ --- дисциплины, входящие в программу обучения второго университета, перечисленные в хронологическом порядке (1ドル \leq b_i \leq n + m$).
Пятая строка входных данных содержит $m$ целых чисел $y_i$ --- рейтинги дисциплин, входящих в программу обучения второго университета, перечисленные том же порядке, что и дисциплины $b_i$ (1ドル \leq y_i \leq 10^9$).
Первая строка выходных данных должна содержать целое число $r$ --- наибольшую возможную сумму рейтингов дисциплин.
Вторая строка выходных данных должна содержать целые числа $l_a,ドル $r_a$ --- позиции в учебной программе первой и последней дисциплин, входящих в план обучения в первом университете, либо <<0 0>>, если студент отказался от стажировки в первом университете.
Третья строка выходных данных должна содержать целые числа $l_b,ドル $r_b$ --- позиции в учебной программе первой и последней дисциплин, входящих в план стажировки во втором университете, либо <<0 0>>, если студент отказался от стажировки во втором университете.
Если возможных правильных ответов несколько, разрешается вывести любой из них.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | 1ドル \leq n, m \leq 50$ |
| 2 | 10 | 1ドル \leq n, m \leq 100$ |
| 3 | 10 | 1ドル \leq n, m \leq 300$ |
| 4 | 10 | 1ドル \leq n, m \leq 500$ |
| 5 | 10 | 1ドル \leq n, m \leq 2000$ |
| 6 | 5 | 1ドル \leq n, m \leq 5000$ |
| 7 | 5 | 1ドル \leq n, m \leq 10,000円$ |
| 8 | 10 | 1ドル \leq n, m \leq 30,000円$ |
| 9 | 10 | 1ドル \leq n, m \leq 100,000円$ |
| 10 | 10 | 1ドル \leq n, m \leq 250,000円$ |
| 11 | 10 | 1ドル \leq n, m \leq 500,000円$ |
7 5 3 1 4 8 6 9 2 2 7 4 10 1 5 3 9 2 11 3 8 3 5 3 4 12
39 2 6 2 4
2 3 1 2 1 4 2 3 1 17 2 15
34 0 0 1 3
3 3 4 2 1 10 1 2 5 4 2 1 2 9
19 1 1 3 3
В первом тесте из условия приведённые планы обучения в университетах приводят к суммарному рейтингу дисциплин $(7 + 4 + 10 + 1 + 5) + (5 + 3 + 4) = 27 + 12 = 39$. Если бы студент выбрал только вторую и третью дисциплины в первом университете и весь курс обучения во втором университете, суммарный рейтинг дисциплин был бы $(7 + 4) + (3 + 5 + 3 + 4 + 12) = 11 + 27 = 38$.
Во втором тесте из условия первая и третья дисциплины во втором университете имеют настолько высокий рейтинг по сравнению с соответствующими дисциплинами в первого университета, что наиболее выгодный вариант --- пройти целиком стажировку во втором университете и отказаться от стажировки в первом университете.