레시피

재민이는 요리를 좋아한다. 그는 $N$일 동안 여러 조리법을 개발하려고 한다. 조리법을 개발하는 과정은 다음과 같다.

• 시장에서 식재료를 사서 냉장고에 넣는다.
• 조리법을 생각한다.
• 냉장고에서 식재료를 꺼내 요리한다.

시장에서는 매일 새로운 종류의 식재료를 판다. $i$번째 날에 파는 식재료의 신선도는 $F_i$이다. 식재료를 사서 냉장고에 보관하면 하루가 지날 때마다 신선도가 1씩 줄어들므로, $i$번째 날에 산 식재료를 $j$번째 날에 꺼내면 신선도가 $F_i - (j - i)$이다. 냉장고에 식재료가 남아 있으면 재민이는 그 재료로 요리하기 전까지 새 식재료를 사지 않는다.

재민이의 $i$번째 날 요리실력은 $C_i$이다. 요리실력이 꾸준히 늘어서 $i < j$인 $i$, $j$에 대해 $0 < C_i \le C_j$를 만족한다. 신선도가 $F$인 식재료를 냉장고에서 꺼내 요리실력 $C$로 요리하면 맛이 $F \times C$인 요리가 만들어진다.

요리하는 날에는 친구 재현이를 초대한다. 재현이는 매우 위생적이어서 냉장고에 있는 식재료가 $i$번째 날에 $L_i$ 이상의 신선도를 가지기를 바란다. 냉장고에 있는 식재료가 그 기준을 채우지 못하면 재민이는 그날 요리하지 못한다. 재현이의 요구사항은 날마다 바뀌어서 $N$일 동안의 기준이 $L_1, L_2, \dots, L_N$으로 주어진다.

새 요리를 만들고 나면 재민이는 다음 날 바로 시장에 가서 식재료를 사고 또 다른 조리법을 생각한다. 식재료가 냉장고에 있는 동안에는 조리법을 고안하며 요리를 미뤄도 되고, 식재료를 산 날 바로 요리해도 된다. 첫째 날에는 냉장고가 비어 있으므로 시장에 가서 식재료를 사고, $N$번째 날에는 반드시 요리해서 냉장고를 비운다.

재민이가 만드는 요리들의 맛의 합의 최댓값을 구하자. 재현이의 까탈스러운 요구사항 때문에 $N$번째 날에 냉장고를 비울 수 없다면 Impossible을 출력한다.

입력은 네 줄로 이루어진다.

첫째 줄에 $N$이 주어진다.

둘째 줄에 $F_1, F_2, \dots, F_N$이 공백으로 구분되어 주어진다.

셋째 줄에 $C_1, C_2, \dots, C_N$이 공백으로 구분되어 주어진다.

넷째 줄에 $L_1, L_2, \dots, L_N$이 공백으로 구분되어 주어진다.

재민이가 만드는 요리들의 맛의 합의 최댓값을 출력한다.

$N$번째 날에 냉장고를 비울 수 없다면 Impossible을 출력한다.

• $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$