P15697 [2018 KAIST RUN Spring] Recipe

Jaemin likes cooking. He wants to devise several recipes for $N$ days. He devises a recipe in the following order. 1. Buy ingredients at a market and put them in a refrigerator. 2. Think of a recipe. 3. Take out ingredients from the refrigerator and cook. He can devise a recipe with such a simple way. He wants to cook delicious food as much as possible. There are new ingredients in the market daily. The ingredients sold on $i$-th day have freshness $F_i$. The freshness $F_i$ of the ingredients in the refrigerator decreases by 1 everyday. If the ingredients are in the refrigerator, he doesn’t buy more ingredients until he cooks with them. He has cooking skill $C_i$ on $i$-th day. His cooking skill advances everyday, so $0 < C_i \le C_j$ for all $i < j$. If he takes out the ingredients which freshness is $F$ from the refrigerator and cook with cooking skill $C$, a dish with a flavor of $F \times C$ is made. When he cooks, he invites his friend Jaehyun, who is very hygienic, so Jaemin hopes that the ingredients in the refrigerator have freshness greater than or equal to $L_i$. If the ingredients don’t satisfy the requirement, Jaemin cannot cook that day. Jaehyun’s requirement varies everyday, and the requirements for $N$ days are given as $L_1, L_2, \dots, L_N$. After he cooks a new dish, he goes to the market the next day to buy new ingredients and think of a new recipe again. Everyday, he may go to the market to buy ingredients, cook, or do nothing for devising a recipe (It is also possible to cook on the day he purchases the ingredients). On the first day, there aren’t any ingredients in the refrigerator, he goes to the market to buy some ingredients. On the $N$-th day, he must cook and empty the refrigerator. Let’s find the maximum sum of a flavor of the dishes he cooks. If it is impossible to empty the refrigerator on the $N$-th day because of Jaehyun’s particular requirements, print out “Impossible” (without quotes).

Input consists of four lines. First line contains $N$. Second line contains $N$ space-separated integers $F_1, F_2, \dots, F_N$. Third line contains $N$ space-separated integers $C_1, C_2, \dots, C_N$. Fourth line contains $N$ space-separated integers $L_1, L_2, \dots, L_N$.

Print the maximum sum of flavors of the dishes Jaemin cooks. If it is impossible to empty the refrigerator on the $N$-th day, print out “Impossible” (without quotes).

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