【题目背景】

友情在积蓄

请，我相信

扑满以后，充满快乐的记忆

勇气在积蓄

来源就是你

每一块，分享的巧克力

【题目描述】

魔仙堡中有 $n$ 个小魔仙，第 $i$ 个小魔仙手中有 $a_i$ 块巧克力，并且每个小魔仙有一个快乐系数 $b_i$。还有一个扑满，扑满有一个快乐值，一开始快乐值为 $0$，魔仙们通过分享自己的巧克力可以让快乐值增加。

每个小魔仙都希望和别人分享手中自己所有的巧克力。具体地，第 $i$ 个小魔仙和第 $j$ 个小魔仙分享巧克力后，扑满会增加 $b_i \times b_j$ 的快乐值。分享是双向的，并且分享的巧克力会被立刻吃掉。因此可以看作两个小魔仙分享一次，这俩手中的巧克力都会少一块。

每个小魔仙手中一开始至少有一块巧克力，且巧克力的总数为 $2n − 2$。并且，如果将一个小魔仙看作一个结点，分享关系看作一条连接了两个结点的边，那么要保证最后形成一个连通图。

魔仙女王想知道小魔仙们能让扑满的快乐值最大变成多少。因为小朋友就要有小朋友的伢子，所以请你帮忙计算一下。

【输入格式】

本题采用特殊输入方式。输入模板见下发文件 $\texttt{io.cpp}$。

第一行三个正整数 $n，m，seed$，代表魔仙的数量，快乐系数的上限，以及随机数种 子。

【输出格式】

一行一个整数，表示扑满的快乐值最大是多少。

【测试点约束】

本题采用捆绑测试。

对于所有测试点：$2 ≤ n ≤ 10^7，1 ≤ a_i < n，1 ≤ b_i ≤ m ≤ 5 × 10^5，0 ≤ seed < 2^{32}$。

每个子任务的具体限制见下表：

下发文件