拆分能量的最大回报

难度：T2

【知识点：记忆化搜索】

前置知识：函数、递归、数组、完整状态与无环依赖。

题目描述

一块能量为 $N$ 的晶石可兑换回报。对能量为 $x$ 的一块：若 $x<2$，只能直接兑换 $x$ 点；否则可以直接兑换 $x$ 点，或者拆成能量 $\lfloor x/2\rfloor,\lfloor x/3\rfloor,\lfloor x/4\rfloor$ 的三块继续分别处理。三块都得到，回报相加。求最大总回报。

规则说明

符号 $\lfloor x\rfloor$ 表示向下取整，即取不大于 $x$ 的最大整数。例如 $\lfloor 7/2\rfloor=3$，$\lfloor 6/2\rfloor=3$。

输入格式

一行一个整数 $N$。

输出格式

一行最大总回报。

样例输入

12

样例输出

13

样例解释

$12$ 拆成 $6,4,3$，各自最优回报为 $6,4,3$，合计 $13$，优于直接兑换 $12$。

数据范围

$0\le N\le10^6$。