Recipe

Time limit1sMemory limit1024 MB

Summary

Buy ingredients on some days, hold each in the fridge until a later day, cook it there if freshness stays at least L_i, and maximize the total of F_i minus elapsed days times C_j; print Impossible if day N can't be a cooking day.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Sorting, Two pointers
Solved: No attempts yet

Problem

Jaemin likes to cook. Over $N$ days he wants to develop several recipes. He develops one like this.

Buy an ingredient at the market and put it in the fridge.
Think up a recipe.
Take the ingredient out of the fridge and cook it.

The market sells a new kind of ingredient every day. The ingredient sold on day $i$ has freshness $F_i$ . An ingredient kept in the fridge loses 1 freshness for each day that passes, so an ingredient bought on day $i$ and taken out on day $j$ has freshness $F_i - (j - i)$ . While an ingredient is still in the fridge, Jaemin does not buy another one before he cooks with it.

On day $i$ Jaemin has cooking skill $C_i$ . His skill keeps growing, so $0 < C_i \le C_j$ holds for $i$ , $j$ with $i < j$ . Taking an ingredient of freshness $F$ out of the fridge and cooking it with skill $C$ makes a dish of taste $F \times C$ .

On a day he cooks he invites his friend Jaehyun. Jaehyun is very hygienic and wants the ingredient in the fridge to have freshness $L_i$ or more on day $i$ . If the ingredient in the fridge misses that standard, Jaemin cannot cook that day. Jaehyun's demand changes every day, so the standards for the $N$ days are given as $L_1, L_2, \dots, L_N$ .

After making a new dish, Jaemin goes to the market the next day, buys an ingredient and thinks up another recipe. While an ingredient sits in the fridge he may spend the day working out a recipe and put the cooking off, and he may also cook on the very day he buys. The fridge is empty on day 1, so he goes to the market and buys an ingredient, and on day $N$ he must cook and leave the fridge empty.

Find the largest possible sum of the tastes of the dishes Jaemin makes. If Jaehyun's fussy demands make it impossible to empty the fridge on day $N$ , print Impossible.

Input

The input has four lines.

The first line contains $N$ .

The second line contains $F_1, F_2, \dots, F_N$ separated by spaces.

The third line contains $C_1, C_2, \dots, C_N$ separated by spaces.

The fourth line contains $L_1, L_2, \dots, L_N$ separated by spaces.

Output

Print the largest possible sum of the tastes of the dishes Jaemin makes.

If the fridge cannot be emptied on day $N$ , print Impossible.

Constraints

$2 \le N \le 250\,000$
$0 < F_i \le 50\,000$
$0 < C_1 \le C_2 \le \dots \le C_N \le 10\,000$
$0 \le L_i \le 50\,000$

Examples3

Example 1
Input
```
3
10 1 1
1 2 3
1 1 1
```
Expected output
```
24
```
Example 2
Input
```
3
10 1 1
1 2 3
10 10 10
```
Expected output
```
Impossible
```

Example 3

Input

10
3 4 1 5 9 2 6 5 3 5
10 11 12 13 14 15 16 17 18 19
1 4 1 4 2 1 3 5 6 2

Expected output