Problem AB3. GPUs

As a modern entrepreneur, you have founded a generative AI startup. The process of generating images, text, etc., is broken down into $N$ tasks, each of which takes one second on one GPU (graphics card). You know in advance when each task will become available—task $i$ at second $T_i$. You have access to an external supercomputer with $M$ GPUs, but each of them has a different cost per second of use—GPU $j$ costs $C_j$ per second.

You must schedule each of the $N$ tasks to a specific GPU $j$ at a specific second, such that this second is not before $T_i$ and no other task is scheduled for the same time and GPU. Again, one GPU works on at most one task in a given second.

Let the final completion time (i.e., the latest scheduled time, plus one) be $F$, and the total paid sum be $S$, i.e., if task $i$ is scheduled for GPU $j$, $S = \sum C_{j_i}$. You must find the minimum possible value of $F \times S$. You will have to solve $Q$ separate, independent instances of the problem.

Constraints

• $1 \le N \le 10^7$
• $1 \le M \le N$
• $0 \le T_i \le N$
• $1 \le C_j \le 2N$
• $1 \le Q \le 5$

Interaction

The task is interactive. Instead of reading from and writing to standard input and output, you must only write a function solveGpus with the following signature:

__int128 solveGpus(
    std::vector<int>& gpuCosts,
    std::vector<int>& reqTimes);

The two vectors of values that the function receives will be sorted in non-decreasing order. It may modify the input vectors. The function returns a type __int128, which represents a 128-bit integer. This is necessary because the answer may exceed the limits of long long. The function may be called multiple times. Each call is an independent instance of the problem.

Your code must not contain a main function, but it may contain any other helper functions, classes, variables, etc. Your code must include the header file gpus.h, in which, for your convenience, an output operator for the __int128 type is also defined. This is done with the following preprocessor directive:

#include "gpus.h"

Your code will be compiled together with a grader that will read from the input and write to the output. On the evaluation system, the only time that counts towards the time limit is the time spent executing your code, i.e., the time for input and output is not counted.

Subtasks

Points for a given subtask are awarded only if all test cases provided for it are passed successfully.

Examples

Input 1

1
8 4
1 2 2 6
0 0 0 0 1 2 2 2

Output 1

39

Note 1

The first 3 tasks in second 0, the next 2 in second 1, and the last 3 in second 2. $S = 13$ $F = 3$