Help for Bit#11518
Hello everyone. My name is Bit and I am the chief accountant of the Republic of Byteland! And recently I was assigned the following task.
There are ministers in Byteland. Each of the ministers considers one minister to be his best friend. Ministers are extremely unusual people: no two ministers consider the same minister their best friend, but perhaps some minister considers himself his best friend!
Recently, a new order came: to assign new salaries to all ministers (a total of new salaries). However, there is a problem: salaries are not necessarily equal! Because of this, some ministers may become upset. Namely: the frustration of the -th minister will be equal to the absolute difference between his salary and the salary of his best friend.
And here is my task: to distribute the salaries so that the maximum frustration among all ministers is as small as possible.
But this task turned out to be too difficult for me. Please help me solve it, otherwise Byteland will be mired in a terrible economic crisis.
The first line contains one number n~(n \le 150) — the total number of ministers.
The second line contains different numbers. The -th number is the number of the minister's best friend under the number .
The third line contains numbers, where the -th number is the size of the next salary. The size of each salary does not exceed 10^9.
The first line should contain the minimum possible maximum frustration of any of the ministers.
The second line should contain numbers separated by a space, where the -th number indicates the amount of salary that was assigned to the -th minister. If there are several optimal salary distributions, output any one.
Example 1
Example 2
Example 3