Problem L: Picky Old Blacksmith

Problem L: Picky Old Blacksmith

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 24  Solved: 7
[Submit][Status][Web Board]

Description

Lanran was born in a poor family in Longmen. Poverty did not weaken his will, but made him determined to stand out and become a great person. When he was \(17\) years old, he made his efforts to become an apprentice to the best blacksmith’s shop in the city. His master was a respected old man who once served as the royal chief weapon master. Also, He was very strict and even picky to his students. One day, the master blacksmith gave all his \(N\) students a mission to forge a sword. After a week, Lanran learnt that all the \(N\) students (including him) had finished their work, and the \(i\)-th student had made a sword with two properties, sharpness \(S_i\) and balance \(B_i\). Lanran also heard that tomorrow the master would score each sword with two preference values \(PS\) and \(PB\), i.e., the score of the \(i\)-th sword would be \(PS · S_i + PB · B_i\). Lanran wished to hand in the best sword tomorrow, i.e., the score of his sword should be higher than any of the other \(N - 1\) swords, so he decided to continue to improve his sword overnight. The night was short, so he decided to finish the work as quick as possible. Lanran knew that to improve the sharpness from \(S\) to \(S+1\) required \(TS\) minutes, and to improve the balance from \(B\) to \(B + 1\) required \(TB\) minutes. So how many minutes at least did Lanran require to improve his sword to become the best sword in tomorrow’s test?

Input

The first line contains five integer \(N, PS, PB, TS, TB, 1 ≤ N ≤ 100, 1 ≤ PS, PB ≤ 500, 1 ≤ TS, TB ≤ 100\), indicating the number of swords, master’s preference to the sharpness and the balance and the required minutes to improve the sharpness and the balance by \(1\).

The second line contains \(N\) integers, \(S_1, S_2, . . . , S_N, 0 ≤ S_i ≤ 500\), indicating the sharpness of the swords.

The third line contains \(N\) integers, \(B_1,B_2, . . . ,B_N, 0 ≤ B_i ≤ 500\), indicating the balance of the swords.

Output

Your answer should contain \(N\) integers in a line separated by a space. For the \(i\)-th integer, it should be the minimum number of minutes required to improve the \(i\)-th sword to have the highest score as if it was made by Lanran.

Sample Input

3 4 2 3 2
1 2 3
9 8 7

Sample Output

5 3 0

HINT

[Submit][Status]