题目描述

U酱有 $n$ 个变量，第 $i$ 个变量对应于英文字母表里的第 $i$ 个小写字母。第 $i$ 个变量的值只能是在区间 $[l_i, r_i]$ 中的一个实数。所有变量的总和不能超过 $m$。保证存在一种合法的变量赋值方案。

U酱用这些变量写了一个算术表达式。这个算术表达式由一个或多个项的总和。每个项恰好是两个不同的变量的乘积，用两个字母表示。例如 ab 表示一个项。没有两个项包含相同的无序变量对。每个项之间用 “+” 号分隔。例如表达式 ab+cd。

求出满足赋值约束条件下的算术表达式最大值。注意即使没有在表达式中出现的变量也需要赋值。

输入格式

第一行包含一个由小写字母和字符“+”组成的表达式 $s$。

第二行包含两个正整数 $n, m$。

第三行包含 $n$ 个整数 $l_1, l_2, \dots, l_n$。

第四行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$。

输出格式

输出一个实数，表示答案。选手输出与标准答案的绝对误差或相对误差不超过 $10^{−9}$ 即视为正确。

ab+ca+bc
3 11
1 2 1
5 4 4

40.333333333333336

数据范围

Subtask $1$（$10$ pts）：保证 $n\leqslant 5$；

Subtask $2$（$20$ pts）：保证 $n \leqslant 10$；

Subtask $3$（$15$ pts）：保证 $n \leqslant 13$；

Subtask $4$（$20$ pts）：保证所有变量都出现了 $n-1$ 次；

Subtask $5$（$35$ pts）：无特殊限制。

对于 $100\%$ 的数据，保证 $2 \leqslant \vert s \vert \leqslant 500$，$1\leqslant n \leqslant 16$，$1 \leqslant l_i \leqslant r_i \leqslant 100$，$\sum l_i \leqslant m \leqslant 1600$。保证 $s$ 由前 $n$ 个小写字母和字符“+”组成。