2825: 饥荒
题目描述
Lzh实在是太饿了。他打算在接下来的n天中自己做菜。每天做一道菜。他能做各种各样的不同的菜。他事先就知道做各道菜的花费以及各道菜对他的好处值。但如果Lzh连续两天做同一道菜，那么第二天得到的该到菜的好处值将是第一天的得到的该道菜的好处值的一半。如果一道菜连续做i(i >= 3)天，那么从第三天开始一直到第i天，Lzh每天从该道菜上得到的好处值将为0。
打个比方来说，Lzh连续3天做同一道好处值为v的菜，那么这三天他得到的好处总值将为1.5*v。
帮助Lzh确定这n天中，每天他该做什么菜，使得做菜的总花费在不超过Lzh现有的钱数的情况下，好处总值最大。
输入
第一行3个数，n（1 <= n <= 21），m（1 <= m <= 50），k（0 <= k <= 100）。n表示Lzh做菜的总天数。m表示Lzh会做的菜的总数。k表示Lzh现有的钱数。
接下来的m行，描述了每道菜的情况。
每行两个数c（1 <= c <= 50），v（1 <= v <= 10000）。c表示该道菜的花费，v表示该道菜的好处值。
输出
仅一行，输出一个数，表示这n天中Lzh能够得到的最大的好处总值。答案保留一位小数。如果不能保证每天都让Lzh吃到菜，则输出0.0。
样例输入 复制
【输入样例一】
2 1 5
3 5
【输入样例二】
3 5 20
2 5
18 6
1 1
3 3
2 3
【输入样例三】
5 1 20
1 5
样例输出 复制
【输出样例一】
0.0
【输出样例二】
13.0
【输出样例三】
7.5
提示
【样例解释一】
Lzh共要做2天菜，他只会做1道菜。该道菜的花费为3，好处值为5。
那他这两2天只能做这道菜，总共的花费为3 + 3 = 6。但他一共只有5块钱。6>5。不能保证他每天都吃到菜，所以输出0.0。
【样例解释二】
一种可行的方案为第1天做第1种菜，第2天做第5种菜，第3天做第1种菜。总花费2 + 2 + 2 = 6 < 20，好处总值为5 + 3 + 5 = 13。
【样例解释三】
连续5天，每天都吃同一道菜。总花费1 + 1 + 1 + 1 + 1 = 5 < 20，由于连续5天吃同一道菜，所以Lzh只有第1天和第2天得到了好处值，后3天得到的好处值为0，所以好处总值为5 + 5 / 2 = 7.5。