题目描述

小 j 有一个为期 $n$ 天的做菜计划。

每天开始时，小 j 可以去买菜；每天结束时，小 j 可以使用买回来的菜做一道菜。

如果一天开始时小 j 手中没有菜，那么他当天一定会去买菜；否则，他当天一定不会买菜。

第 $i$ 天买回来的菜的新鲜度为 $F_i$。之后每经过一天，其新鲜度会减少 $1$。

给定一个序列 $C_i$。若小 j 在第 $i$ 天做菜，且当前使用的菜的新鲜度为 $f$，那么这道菜产生的价值为

如果在第 $i$ 天做菜，则要求当前菜的新鲜度不低于 $L_i$。

第 $n$ 天结束时，手中不能有剩余的菜。

求能够获得的最大价值总和。如果不存在满足要求的方案，输出 Impossible。

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个整数

第三行包含 $n$ 个整数

第四行包含 $n$ 个整数

输出格式

若存在合法方案，输出一行一个整数，表示最大价值总和。

若不存在合法方案，输出：

Impossible

样例 1

输入

3
10 1 1
1 2 3
1 1 1

输出

24

样例 2

输入

3
10 1 1
1 2 3
10 10 10

输出

Impossible

样例 3

输入

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

数据范围与提示

• 对于 $25\%$ 的数据，$n\le 1000$；

• 对于全部测试数据：

  $$2\le n\le 2.5\times 10^5,$$ $$0<F_i\le 10^6,$$ $$0<C_i\le 10^6,$$ $$0\le L_i\le 10^6.$$