Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly. Also, try not to use custom input, because the checker is specialized on test cases to check your submissions faster. Try to check your code on your own.

Problem statement

There are \(N+1\) stones, numbered \(1 , 2 , … , N + 1\). For each \(i ( 1 ≤ i ≤ N )\), the height of stone \(i\) is \(h_i\) and the value of stone \(i\) is \(a_i\). There is a frog who is initially on stone 1. He will repeat the following action some number of times to reach stone \(N+1\) : If the frog is currently on stone \(i\), he can jump to the \(j\) -the stone if all of the following conditions are met:

\(i ≤ j ≤ n\)
The height of the jump is no more than the width of the jump. Here, the height of the jump is defined as a maximum \(h_i , h_{i + 1} , … h_j \), and width as \(j − i + 1\).
The cost of the jump is \(\sum\limits_{l=i}^{j}\sum\limits_{r=i(l \ne r)}^{j} a_l*a_r\).
After, he will automatically go to \(j + 1\) -the stone.

Also, the frog has his lucky number \(k\) and he wants to reach stone \(N+1\) in \(k\) steps so that sum of costs was minimized. Your task is to calculate the minimum sum of costs for him and find optimal jumps.

Input format

The first line contains two integers \(N\) and \(k\) (\(1≤N≤10^4,1≤k≤min(n, 50)\)) — the length of the arrays and the number of jumps
The second line contains \(N\) integers \(h_1,h_2,…,h_n(1≤h_i≤n)\) — the array \(h\)
The third line contains \(N\) integers \(a_1,a_2,…,a_n(1≤a_i≤10^5)\) — the array \(a\)
It is guaranteed that we can achieve \(N+1\)-th stone in \(k\) steps.

Output format

The first line contains one integer - the optimal sum of costs. Next \(k \) lines contain two numbers - pairs \(i_1, j_1, . . . i_k, j_k\), where \(l_1 = 1, r_k = n, i_t ≤ j_t\) , and \(l_t = r_{t−1} + 1\) for all \(t>1\)– the jumps of the frog.

Verdict and scoring :

There are 6 test cases(with sample). Your score will be calculated by the following rule: for each non-sample test case, you will get \(min(20, 20*\frac{ja+1}{pa+1})\) scores, and 0 scores for the sample. Here ja - jury's sum of costs, pa - your sum of costs. If your output does not coincide with the output format, you will get 0 scores on test.