该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

这是孵化器实验室第二轮考核第一期的E题附加题，旨在考查大家简单（?）的动态规划算法 还有题面阅读能力

Tips:搜索"01背包问题"

背景吧大概

梦幻的一缕灵感

一动不动也好热的夏天已经进入了尾声，你抬头望向天空，无际的湛蓝中氤氲着期待的味道。任由思绪徜徉在晴空，你被带到了梦与现实的交界。

睁 大 眼 睛 ~

要融化在蔚蓝色的诱惑里啦，这样可不行！你决心给这片空旷的穹顶添乱——天空的30%任你装点，要塞些好玩的云朵~

✰松软✰

想抱着玩~

趁你没有完全清醒，让我们假装有一个可变的天空面积~

重复的云朵和寻常的云朵都不要，向下取整的30%天空面积必须妥善利用。

对于每一朵候选云彩，我们都将给出将占用的面积数值和美学分数。

装点最可爱的天空吧！

Format

音put

输入的第一行是双目所及的天空总面积。

接下来，将有数目 随心所欲~ 的输入行。

每一个输入行代表一朵候选云朵，包含两个本云朵的正整数参数，其一是这朵云将占用的天空面积，其二是将这朵云装点得到的美学分数。

测量云不是该用体积吗~？

嗷put

在可能得到的天空中，最可爱的天空会得到几分呢？

利用不超过天空总面积的30%，塞入总分尽可能高的云朵~

输出一个整数，为可能的最高美学价值总分。

Sampos

797
240 12345
230 2
9 37

39

Fuwafuwa Limitation

1s, 1024KiB for each test case.

数目 随心所欲~ 的输入行大概也不超过128行吧。

天空面积的30%应该也不会大于20039个单位？

✰ 玩 得 开 心 ✰

格式检查睡着了~放肆地为输出的行末添加不限数目的空白符！

输出文件容器提出严正抗议。

数据已削弱

30%的数据可由未优化的普通算法通过。

在能够通过30%的数据以后，考虑优化现有算法。