U54047.鼠鼠的奖励

由于鼠鼠被资本做局了,只有一个容量为$C$的背包.于是神明奖励他拾取$q$个物品.

如果鼠鼠拾取的物品超过剩余物品价值的一半或已经拾取物品价值的一半,神明就会收回所有物品,觉得他太贪心了.(不包括第一次)

如果鼠鼠拾取的物品低于已经拾取物品价值的四分之一,神明就会收回所有物品,觉得他好欺负.(不包括第一次)

请你帮主鼠鼠获得最多的钱.

第一行输入$C$ 和 $q$.
接下来 $q$ 行分别输入每个物品的价值与重量.

输出最多能能获得多少钱