P15697 [2018 KAIST RUN Spring] Recipe

Jaemin 喜欢烹饪。他想要为接下来的 $N$ 天设计几道食谱。他按照以下顺序设计食谱： 1. 去市场购买食材，并将它们放入冰箱。 2. 构思食谱。 3. 从冰箱中取出食材并进行烹饪。 他可以用这种简单的方式来设计食谱。他希望能够烹饪出尽可能多的美味佳肴。 市场上每天都有新的食材。第 $i$ 天售卖的食材新鲜度为 $F_i$。冰箱中食材的新鲜度每天会减少 $1$。如果冰箱中已有食材，在他用这些食材烹饪之前，他不会购买更多食材。 他在第 $i$ 天的烹饪技能为 $C_i$。他的烹饪技能与日俱增，因此对于所有 $i < j$，都有 $0 < C_i \le C_j$。如果他取出新鲜度为 $F$ 的食材，并以烹饪技能 $C$ 进行烹饪，那么他将制作出一道风味值为 $F \times C$ 的菜肴。当他烹饪时，他会邀请他的朋友 Jaehyun，Jaehyun 非常注重卫生，因此 Jaemin 希望冰箱中食材的新鲜度不低于 $L_i$。如果食材不满足这个要求，Jaemin 当天就无法烹饪。Jaehyun 的要求每天都会变化，$N$ 天的要求依次给定为 $L_1, L_2, \dots, L_N$。 在他烹饪完一道新菜肴后，他会在第二天去市场购买新的食材，并再次构思新的食谱。每天，他可以选择去市场购买食材、烹饪、或者为了设计食谱而什么都不做（也可以在购买食材的当天进行烹饪）。第一天，冰箱里没有任何食材，他会去市场购买一些食材。在第 $N$ 天，他必须进行烹饪并清空冰箱。让我们找出他烹饪的菜肴风味值总和的最大值。如果由于 Jaehyun 的特殊要求，无法在第 $N$ 天清空冰箱，则输出 “Impossible”（不包含引号）。

输入包含四行。 第一行包含一个整数 $N$。 第二行包含 $N$ 个由空格分隔的整数 $F_1, F_2, \dots, F_N$。 第三行包含 $N$ 个由空格分隔的整数 $C_1, C_2, \dots, C_N$。 第四行包含 $N$ 个由空格分隔的整数 $L_1, L_2, \dots, L_N$。

输出 Jaemin 烹饪的菜肴风味值总和的最大值。如果无法在第 $N$ 天清空冰箱，则输出 “Impossible”（不包含引号）。

### 数据范围 - $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$ 翻译由 DeepSeek V3.2 完成