Даны двухчашечные весы и набор гирек. На левую чашу весов положили взвешиваемый предмет весом K граммов. Можно ли привести весы в состояние равновесия, и если можно, то определите для каждой чаши весов, какие гирьки на нее для этого нужно положить. Имеющиеся гирьки разрешается класть на любую из чаш весов (каждая гирька имеется только в одном экземпляре, некоторые гирьки можно не использовать).

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из \(n\) деталей, пронумерованных от 1 до \(n\), при этом деталь с номером \(i\) изготавливается за \(p_i\) секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.

На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое.

Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "abcdefghijklmnopqrstuvwxyz" равна 25, а строки "abdc" — только 1.

Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и поможете ему с ней справиться.

Победитель студенческой олимпиады получил предложения о стажировке от двух университетов. При подготовке планов обучения он узнал рейтинг качества преподавания каждой дисциплины в этих университетах.

Программа обучения первого университета состоит из последовательности перечисленных в хронологическом порядке n различных дисциплин a₁, a₂, ..., a_n, имеющих рейтинги x₁, x₂, ..., x_n соответственно. Программа обучения второго университета состоит из последовательности перечисленных в хронологическом порядке m различных дисциплин b₁, b₂, ..., b_m, имеющих рейтинги y₁, y₂, ..., y_m соответственно.

Студент имеет возможность составить план обучения в первом университете таким образом, чтобы изучить дисциплины на позициях учебной программы с l_a по r_a включительно (1 ≤ l_a ≤ r_a ≤ n), либо отказаться от стажировки в первом университете. Аналогично он может составить план обучения во втором университете таким образом, чтобы изучить дисциплины на позициях учебной программы с l_b по r_b включительно (1 ≤ l_b ≤ r_b ≤ m), либо отказаться от стажировки во втором университете.

Изучать одну и ту же дисциплину дважды в разных университетах не имеет смысла, поэтому все дисциплины в двух выбранных планах обучения должны быть различны.

Требуется написать программу, которая определит планы обучения студента таким образом, чтобы получить наибольшую возможную сумму рейтингов изучаемых дисциплин.