Завдання № 19
відбірково-тренувальних зборів
команди міста Києва


за матеріалами ІІІ (міського) етапу 2006 року

1. Кур’єри

Максимальна оцінка: 100 балів
Обмеження на час: 2 сек.
Обмеження на пам’ять: 64 МБ
Вхідний файл: courier.in
Вихідний файл: courier.out
Програма: courier.*


У місті Х є пряма вулиця Товстунів. Всі її мешканці, за дивним збігом обставин, дуже люблять добряче попоїсти. Компанія ННС («Нагодуємо навіть слона») вирішила заробити на цьому гроші. Вона розгорнула широку мережу доставки їжі замовникам. На вулиці одночасно й постійно перебувають N кур'єрів. Після отримання замовлення компанією продукти доставляє кур’єр, що перебував у момент отримання замовлення найближче до будинку замовника. Вважати, що такий кур'єр завжди єдиний і доставка ним замовлення відбувається миттєво. Надалі кур'єр залишається чекати наступного замовлення вже на цьому новому місці.

Завдання
Визначити сумарну відстань, яку пройдуть усі кур'єри при виконанні всіх замовлень.

Вхідні дані
Перший рядок містить два цілих числа:
N (2 ≤ N ≤ 100 000) — кількість кур'єрів;
M (0 ≤ M ≤ 100 000) — кількість замовлень.

Другий рядок містить N натуральних чисел X1, X2, … , XN. Тут Xi — координата почат­кового положення i-го кур'єра на вулиці Товстунів, 1 ≤ Xi ≤ 1 000 000 000.

Третій рядок містить M натуральних чисел Y1, Y2, ... , YM. Тут Yj — координата будинку j-го замовника з вулиці Товстунів, 1 ≤ Yj ≤ 1 000 000 000.

Вихідні дані
Вихідний файл має містити лише одне ціле число — шукану сумарну відстань, яку подолають кур'єри.

Приклади

courier.incourier.out
3 6
5 11 3
7 8 5 1 12 4
13


2 5
2 3
1 1 1 1 1
1


2. Робочий календар

Максимальна оцінка: 100 балів
Обмеження на час: 2 сек.
Обмеження на пам’ять: 16 МБ
Вхідний файл: calendar.in
Вихідний файл: calendar.out
Програма: calendar.*

На планеті Олімпія місяць триває N тижнів, а в кожному тижні M днів. Пересічний мешканець Олімпії сам формує свій робочий графік, але у зв’язку з магнітними бурями одні дні сприятливі для його роботи, а інші ні. У мешканця є календар на місяць, у якому для кожного дня написано «число сприятливості». Це число вказує на те, наскільки відповідний день сприятливий для роботи.

Робочий графік складається з довільної кількості дводенних змін. Другий день кожної зміни завжди за календарем або наступний після першого дня, або саме через тиждень після першого дня. Можна розпочинати нову робочу зміну, не закінчивши попередні. Кожен день місяця може належати не більше, ніж одній зміні. Всі зміни потрібно завершити до кінця місяця.

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

Вхідні дані
В першому рядку вхідного файла записано два натуральних числа через прогалину: N і М (1 ≤ N ≤ 100, 1 ≤ M ≤ 10). Далі у файлі записано календар: N рядків по M цілих чисел у кожному рядку. i-е число j-го рядка — це число сприятливості i-го дня j-го тижня календаря. Кожне таке число є цілим і за абсолютним значенням (модулем) не перевищує 100.

Вихідні дані
Вихідний файл має містити лише одне ціле число — максимально можливе сумарне число сприятливості для робочих днів жителя планети Олімпія.

Приклад

calendar.incalendar.out
3 4
1 3 3 -7
2 -2 -6 5
-3 -4 -5 -6
11



Пояснення до прикладу
Найкращий робочий графік виглядає так: перша робоча зміна — перший день першого тижня і перший день другого тижня, друга робоча зміна — другий і третій дні першого тижня, третя робоча зміна — четвертий день другого тижня і перший день третього тижня. Сумарне число сприятливості дорівнює 1 + 2 + 3 + 3 + 5 + (–3) = 11.

3. Острови

Максимальна оцінка: 100 балів
Обмеження на час: 2 сек.
Обмеження на пам’ять: 64 МБ
Вхідний файл: islands.in
Вихідний файл: islands.out
Програма: islands.*


Далеко в океані знаходиться держава, розташована на архіпелагу з N островів, (N ≤ 100 000). Між деякими з островів збудовано мости. Між довільними двома островами існує не більше одного маршруту, в якому кожен міст проходять лише один раз вздовж цього маршруту. Геологічні дослідження виявили, що майже усі острови здатні приносити чималий зиск від видобутку кольорових металів у копальнях. На жаль, інженерні обрахунки показали, що міст може зруйнуватись, якщо він сполучає острови, на яких одночасно працюють шахти. Отже, якщо по обидва боки мосту працюють копальні, то цей міст необхідно буде закрити. Закриття мостів створює багато незручностей, тому держава виділяє кошти, щоб упоратися з незадоволенням мешканців.

Завдання
Задано опис мостів, які сполучають острови, а також штраф за закриття кожного з мостів. Для кожної шахти відомо, який вона дає прибуток, коли працює. Потрібно вказати такий набір островів, на яких треба проводити видобувні роботи, щоб принести державі максимальний зиск. Зиск — це різниця суми прибутків з працюючих шахт та суми штрафів за закриті мостові з’єднання.

Вхідні дані
Перший рядок файлу islands.in містить два натуральних числа: N — кількість островів і M — кількість мостів.

Другий рядок містить послідовність N натуральних чисел: j-те число — прибуток, який буде приносити шахта на острові j.

В наступних M рядках задано опис мостів. В кожному з цих рядків — три числа — номери островів, які з’єднуються цим мостом (острови нумерують натуральними числами від 1 до N), а також штраф за закриття даного мосту. Прибуток від шахти і штраф за закриття мосту — натуральні числа, що не перевищують 10 000.

Вихідні дані
Сформуйте відповідь до задачі у файл islands.out за таким принципом:

Оцінювання
За правильну величину зиску вам буде зараховано 30% балів за відповідний тест. Якщо ваш набір островів виявиться одним з оптимальних, то вам буде зараховано 70% балів за відповідний тест. Бали за обидві частини задачі нараховують незалежно. Не менш, ніж у 40% тестів N ≤ 1 000.

Приклади

islands.inislands.out
7 5
10 70 70 5 5 1 1
1 2 8
2 3 30
3 4 5
3 6 2
2 7 2
117
4 1 2 3 5





7 5
10 70 70 6 5 1 1
1 2 8
2 3 30
3 4 5
3 6 2
2 7 2
118
5 1 2 3 4 5