No.2008 Super Worker
Kiri8128
KazunProblem Statement
Kiri has a part-time job. Initially, Kiri's job level is $1$. There are $N$ jobs, and she has decided to take on all of them in any order she likes. If she does the $i\ (1 \le i \le N)$-th job when her job level is $x$, she receives a salary of $A_i \cdot x$, and then her job level becomes $B_i \cdot x$. What is the maximum possible total salary she can earn? Output the answer modulo $10^9+7$.
Input
$N$ $A_1\ A_2\ \cdots A_N$ $B_1\ B_2\ \cdots B_N$
$1 \le N \le 2 \times 10^5$
$1 \le A_i,\ B_i \le 10^6\ (1 \le i \le N)$
All inputs are integers.
Output
Output the maximum possible total salary modulo $10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
2 30 20 2 3
Output
110
[If job $1$ is done first]
She can earn $30$ from job $1$ and $40$ from job $2$, for a total salary of $70$.
[If job $2$ is done first]
She can earn $20$ from job $2$ and $90$ from job $1$, for a total salary of $110$.
Therefore, the maximum amount she can earn is $110$.
Sample 2
Input
2 7000 1000000 1000000 1
Output
0
Note that you must output the remainder modulo $10^9+7$.
Sample 3
Input
8 3 14 15 92 65 35 89 79 2 7 1 8 2 8 1 8
Output
2048669
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。