Blackjack#12323
You are playing a game of blackjack against a dealer named Silly Andryusha. Andryusha finds regular blackjack too simple, so he invented his own, significantly more complicated rules.
In front of you on the table lies a row of cards, numbered from to . On card , there is a number a_i — the base score of this card. Under card , there are: k_i aces, each ace has a value of x_i points.
You play one round and can make exactly one move. Choose a non-empty subarray of cards , where 1 \leq L \leq R \leq n and reveal card . Andryusha allows you to use the aces that lie under it.
Next, you distribute these aces according to Andryusha's rules: if R - L + 1 \ge k_L, — choose exactly k_L different cards among and add x_L points to each, if R - L + 1 \le k_L, — add x_L points to all cards in the segment .
Your score is the sum of the values of the cards in the segment after applying the aces.
Since Silly Andryusha is a streamer and is already earning too much, your task is to collect the maximum possible number of points while playing by his rules.
The first line contains the number — the number of cards (1 \le n \le 5 \cdot 10^5).
The second line contains integers a_1, a_2, a_3, \ldots, a_n (|a_i| \le 10^9) — the base score on each card.
The third line contains integers k_1, k_2, k_3, \ldots, k_n (0 \le k_i \le n) — the number of aces that lie under each card.
The fourth line contains integers x_1, x_2, x_3, \ldots, x_n (0 \le x_i \le 10^9) — the number of points that one ace under the corresponding card gives.
Output one integer — the maximum possible number of points that can be obtained in one move by choosing a subarray and applying the aces according to Silly Andryusha's rules.
Example 1
Example 2
In the first set of input data, it is beneficial to take the subarray . In this case, the number of aces is , so there are enough to add points to each card in the segment. The total sum is -2 + 4 + 10 + 10 = 22.
In the second set of input data, it is beneficial to take the subarray . The number of aces is , so there are enough to add points to both cards. The final sum is 1 + 5 + 4 + 4 = 14.
Subtask ( points) : (n \le 5000)
Subtask ( points) : (k_i = 0 or x_i = 0)
Subtask ( points) : (k_i = n, x_1 = x_2 = x_3 =\cdots = x_n)
Subtask ( points) : (k_i = n, x_i \ge max(|a_i|))
Subtask ( points) : (x_i = 1)
Subtask ( points) : (k_i \le 50)
Subtask ( points) : (k_1 \le k_2 \le k_3 \le \cdots \le k_n, x_1 = x_2 = x_3 = \cdots = x_n)
Subtask ( points) : (x_1 = x_2 = x_3 = \cdots = x_n)
Subtask ( points) : (k_i = n)
Subtask ( points) : (n \le 100000)
Subtask ( points) : Without additional constraints