Допомога Біту#11518

Допомога Біту

1 секунда

256 мегабайтів

Дуже складна

Вітаю всіх! Мене звати Біт, і я головний бухгалтер республіки Байтландія! Нещодавно мені доручили виконати наступне завдання.

У Байтландії є $n$ міністрів. Кожен міністр вважає одного міністра своїм найкращим другом. Міністри дуже своєрідні: жодні два міністри не вважають одного і того ж міністра своїм найкращим другом, хоча можливо, що міністр вважає найкращим другом самого себе!

Нещодавно надійшло нове розпорядження: призначити всім міністрам нові зарплати (всього $n$ нових зарплат). Проте є проблема: зарплати можуть бути різними! Через це деякі міністри можуть засмутитися. Зокрема, засмучення $i$ -го міністра дорівнює абсолютній різниці між його зарплатою та зарплатою його найкращого друга.

Моє завдання — розподілити зарплати так, щоб максимальне засмучення серед усіх міністрів було якомога меншим.

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

Вхідні дані

Перший рядок вводу містить одне число $n (n \leq 150)$ n~(n \le 150) — загальна кількість міністрів.

Другий рядок містить $n$ різних чисел. $i$ -е число є номером найкращого друга міністра під номером $i$ .

Третій рядок містить $n$ чисел, де $i$ -е число — це розмір чергової зарплати. Розмір кожної зарплати не перевищує $1 0^{9}$ 10^9.

Вихідні дані

У першому рядку виведіть мінімальне можливе максимальне засмучення серед усіх міністрів.

Другий рядок повинен містити $n$ чисел, розділених пробілом, де $i$ -е число позначає розмір зарплати, яку призначили $i$ -му міністру. Якщо існує декілька оптимальних розподілів зарплат, виведіть будь-який.

Приклади

Приклад 1

Приклад 2

Приклад 3