暂无测试数据。

大学选课真的是一件很苦恼的事呢！

Marco：“我要两年毕业！我要选尽量多的学分！这些课统统选上！”

长者："你啊，Too Young！你看看作业量，你做的完吗？"

Marco（笑容逐渐消失.gif）：”那可咋整啊?“

长者："还能咋整？退课呗！“

已知 Marco 选了 $N(1 \leq N \leq 500)$ 门课，每门课有学分 $w_i$ ，劳累度 $v_i$ 和挂科概率 $p_i$ ；

其中，$w_i$ 为 $[1,5]$ 范围内的一个正整数，$v_i$ 是 int 范围内正整数， $p_i$ 是 $[0,1]$范围内小数；

现在 Marco 想退掉某些课使得自己的劳累度尽量小，但是，如果 Marco 的学分总数达不到给定的 $MINX$，他会被退学。

Marco想知道，在期望学分大于等于 $MINX$ 的情况下，他的最小劳累度是多少。

注意：如果一门课挂科，Marco 将付出 $v_i$ 的劳累度但是无法获得相应学分；否则，Marco 将付出 $v_i$ 的劳累度并收获 $w_i$ 的学分。

输入格式

第一行一个正整数 $N$ 表示课程数量

接下来 $N$ 行，每行空格分开的 $3$ 个数 $w_i,v_i$ 和 $p_i$ ，含义如题面所述

最后一行一个正整数 $MINX$ 表示所需最小学分。

输出格式

一行一个正整数表示最小劳累度。

数据范围

本题共 $10$ 个测试点，每个测试点 $10$ 分。

对于 $10\%$ 的数据，$1 \leq N \leq 10$

对于 $30\%$ 的数据，$1 \leq N \leq 20$

对于另外 $20\%$ 的数据，$p_i=0$

对于 $100\%$ 的数据，

$1 \leq N \leq 500$ ，

$w_i$ 是正整数且 $1 \leq wi \leq 5$，

$p_i$ 最多包含 $2$ 位小数且 $0 \leq pi \leq 1$，

$v_i$ 是 int 范围内正整数.

保证全选的情况下 Marco 不会被退学。

2
1 233 0
2 1 0.5
1

1