Задача №114790. Зачет в третьей параллели
Один преподаватель придумал новый формат проведения зачета.
- Зачет состоит из \(n\) блоков, каждый из которых соответствует одной из пройденных тем; за \(i\)-й блок для всех \(i\) от \(1\) до \(n\) независимо от других ставится оценка \(c_i\);
- Оценка за каждый блок может принимать любое целое значение от \(0\) до \(100\) включительно, и может быть получена на выбор ученика либо ответом на теоретический вопрос , либо решением практической задачи ;
- Зачет считается успешно сданным, если хотя бы \(a\) блоков были сданы ответом на теоретический вопрос и хотя бы \(b\) блоков были сданы решением практической задачи;
- При соблюдении предыдущего условия итоговая оценка за зачет \(C\) вычисляется как сумма оценок за все блоки, то есть \(C = \sum\limits_{i=1}^n c_i\).
Илья собирается сдавать зачет. Илья достаточно хорошо представляет уровень своих знаний по каждой теме, и уверен, что сдавая \(i\)-й блок теорией, получит оценку \(x_i\), а сдавая его же практикой — оценку \(y_i\). Помогите ему определить, какие из блоков (не менее \(a\)) ему следует сдавать теорией, а какие (не менее \(b\)) — практикой, чтобы набрать максимально возможный суммарный балл за зачет.
В первой строке входных данных через пробел перечислены три целых числа \(n\), \(a\) и \(b\) — общее количество тем, а также минимальное количество тем, которые необходимо сдать теорией и практикой, соответственно (\(1 \leqslant n \leqslant 2 \cdot 10^5\); \(0 \leqslant a, b \leqslant n\)). Гарантируется, что \(a + b \leqslant n\).
Во второй строке через пробел перечислены \(n\) целых чисел \(x_i\) — оценки, которые получит Илья, если будет сдавать блоки, отвечая на теоретические вопросы (\(0 \leqslant x_i \leqslant 100\)).
В третьей строке так же перечислены \(n\) целых чисел \(y_i\) — оценки, которые он получит, решая практические задачи (\(0 \leqslant y_i \leqslant 100\)).
В первой строке выведите одно целое число \(C\) — максимальную суммарную оценку, которую Илья может получить за зачет.
Во второй строке выведите \(n\) разделеленных пробелами символов, \(i\)-й из которых равен « T », если Илье стоит отвечать в \(i\)-м блоке теорию, и « P », если практику. Хотя бы \(a\) символов должны быть равны « T », и хотя бы \(b\) равны « P ».
4 1 1 10 30 50 70 80 60 40 20
260 P P T T
4 1 1 30 40 60 90 10 25 50 85
215 T T T P
4 2 1 0 17 70 13 2 21 55 99
190 T P T P