You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

$lyx$正在游戏中创建自己的国家，为帮助新城市建立连接，需要送货员$Sam$将开罗尔物质送到新城市，同时$lyx$想要运送尽可能贵重的普通货物以促进新城市的发展，你能计算出运送货物的最大价值吗

为简化问题，我们将$Sam$的背包视为 $3X3$ 的二维空间，将开罗尔物质和普通货物的体积视为 $1X1$，$2X2$ 或者 $3X3$ 的空间，给出若干可供选择的货物和开罗尔物质的体积，判断运送货物的最大价值

Format

Input

每个测试点只有一组测试数据

第一行一个正整数 $n(1 \leq n \leq 1e5)$ 代表普通货物的数量

然后有 $n$ 行：

第 $i$ 行有两个用空格隔开的整数 $x(1 \leq x \leq 1e5)$ 和 $y(1 \leq y \leq 3)$ ，代表一个价值为 $x$ 体积为 $yXy$ 的货物

最后一行一个正整数 $m(1 \leq m \leq 3)$ 代表体积为 $mXm$ 的开罗尔物质

Output

输出一个整数代表运送货物的最大价值

Samples

5
33 2
57 3
25 3
18 1
55 1
1

106