训练排期

题目背景

“森林运动会”临近，乐柠兔准备在接下来的 $n$ 天里做系统训练。她每天都要安排一个训练项目来保持状态。

她掌握了 $m$ 种不同的训练项目。对于每个项目，她事先知道：

• 需要消耗的 训练券 数量（相当于资源或场地费）；
• 带来的 士气值（训练后的成就感与状态提升）。

但是有一个“疲劳衰减”规则：

• 如果 连续两天 安排同一个项目，则第二天该项目获得的 士气值仅为第一天的一半；
• 如果 连续第 3 天及之后 仍是同一项目，则从第 3 天起士气值为 $0$。

例如：若连续 3 天都是某个基础士气值为 $v$ 的项目，则 3 天合计士气为：

乐柠兔希望在 保证每天都有训练 的前提下，在 总训练券不超过 $k$ 的条件下，使 总士气值最大。请你计算这个最大值。

输入格式

• 第一行三个整数 $n, m, k$：
  • $n$：训练天数（$1 \le n \le 21$）；
  • $m$：训练项目种类数（$1 \le m \le 50$）；
  • $k$：可用训练券总数（$0 \le k \le 100$）。
• 接下来 $m$ 行，每行两个整数 $c, v$：
  • $c$：该项目单日所需训练券（$1 \le c \le 50$）；
  • $v$：该项目单日基础士气值（$1 \le v \le 10000$）。

输出格式

• 输出一行，一个实数：在不超过训练券预算的前提下，乐柠兔能获得的 最大总士气值。
• 答案保留 1 位小数。
• 若无法保证每天都有训练，则输出 0.0。

样例输入 1

3 5 20
2 5
18 6
1 1
3 3
2 3

样例输出 1

13.0

说明： 一种可行安排是：

• 第 1 天选项目 1；
• 第 2 天选项目 5；
• 第 3 天再选项目 1。

总消耗 $2+2+2=6 \le 20$，总士气为 $5+3+5=13$。

样例输入 2

5 1 20
1 5

样例输出 2

7.5

说明： 连续 5 天都训练同一项目，花费 $1 \times 5 = 5 \le 20$， 总士气为：

数据范围与说明

• $1 \le n \le 21$
• $1 \le m \le 50$
• $0 \le k \le 100$
• $1 \le c \le 50$
• $1 \le v \le 10000$