You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

在被迷雾笼罩的算法王国里，大魔导师 $1h$ 研究出了一种神秘的能量函数——任何二叉树都被赋予一个权值。传说构造出权值最大的那棵树的人，将会继承大魔导师的称号。你，是否有勇气挑战 $1h$ 的试炼？

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

Description

给定整数系数 $d_0, d_1, d_2$，定义一棵二叉树的权值为：

其中：

• $ct_0$：度为 0（叶子）的节点数；
• $ct_1$：度为 1 的节点数；
• $ct_2$：度为 2 的节点数。

现在给定整数 $n$（总节点数）和 $x$（叶子节点数），请在所有包含 $n$ 个节点且叶子数为 $x$ 的二叉树中，求出 最大可能的权值 $W_{\text{max}}$。

Format

Input

一行五个整数：

约束：

• $1 \le n \le 10^5$
• $1 \le x \le n$
• $d_0, d_1, d_2 \in [-10^9, 10^9]$（可以为负）

注意：若输入的 $x$ 在二叉树的可行范围之外（例如 $x>\frac{n+1}{2}$），则视为无效输入（题目保证输入合法）。

Output

输出一个整数：该树能达到的最大权值 $W_{\text{max}}$。

Sample

Input

7 4 3 2 1

Output

15