题目描述

有 $n$ 个物品，每个物品的美观值为 $a_i$，价值为 $b_i$。

小红喜欢漂亮的东西，所以他不希望买下的物品的美观值有低的，同时他希望买到的价值之和尽可能大。

从 $n$ 个物品中选择至多 $k$ 个物品，满足这 $k$ 个物品中美观值的最小值乘以 $k$ 个物品的价值之和得到的结果最大。

输入格式

由于本题输入量过大，使用生成式输入

第一行两个整数 $n,k$。

第二行两个整数，表示 $s1,s2,key$。

数组 $a$ 和 $b$ 由 $s1,s2,key$ 和代码生成,请选手在提交的代码中选择合适位置生成数组 $a$ 和 $b$ ,这里提供cpp代码.

void decode(long long n,long long s1,long long s2,long long key){
    for(long long i = 1;i <= n;i++){
        a[i] = s1;
        b[i] = s2;
        s1 = (25214903917 * s1) & key;
        s2 = (25214903917 * s2) & key;
    }
}

输出格式

一行一个整数,具体见题面

样例 #1

样例输入 #1

4 2
1 3 15

样例输出 #1

162

样例 #2

样例输入 #2

20 5
114 514 65535

样例输出 #2

11631120180

提示

样例 $1$ 生成得到的物品 $(a_i,b_i)$ 如下:

选择 $2,3$ 两个物品,答案为 $min(13,9) * (7 + 11) = 162$

对于 $30\%$ 的数据：$1\leq n\leq 1000$

对于 $70\%$ 的数据：$1\leq n\leq 10^5$

对于 $100\%$ 的数据：$1\leq n\leq 10^7,1\leq a_i,b_i\leq 10^5$ $0\leq k\leq n$