405140: GYM101806 R 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 food as delicious 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 ≤ C_j for all i < j. If he takes out the ingredients whose freshness is F from the refrigerator and cook with cooking skill C, a dish with a flavor of F × 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₁,  L₂,  ...,  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. (2 ≤ N ≤ 250, 000)

Second line contains N space-separated integers F₁, F₂, ..., F_N. (0 < F_i ≤ 50, 000)

Third line contains N space-separated integers C₁, C₂, ..., C_N. (0 < C₁ ≤ ... ≤ C_N ≤ 10, 000)

Fourth line contains N space-separated integers L₁, L₂, ..., L_N. ( 0 ≤ L_i ≤ 50, 000)

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).

3
10 1 1
1 2 3
1 1 1

24

3
10 1 1
1 2 3
10 10 10

Impossible

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

526