Ciel and Karaoke

All submissions for this problem are available.
You need to find the distance from the given piecewiseconstant function to the set of all functions, satisfying Lipschitz condition with the constant K, in the space L^{1}(−∞, +∞). If you understand nothing here then read the problem statement below :P
Chef Ciel and her friends go to karaoke after the New Year's party. In karaoke, they sing songs, and moreover, recent karaoke machines can score their performance. To get a high score, one of the most important things is to sing with correct pitches.
The correct pitch at time t for some song is represented as f(t), where f(t) is a piecewiseconstant function. In this problem, let us consider the infinitely long time −∞ < t < +∞ for simplicity. Let N−1 integers A_{1} < A_{2} < ... < A_{N−1} denote the time moments when the correct pitch is changed. That is,
 f(t) = B_{0}, for −∞ < t < A_{1},
 f(t) = B_{k}, for A_{k} ≤ t < A_{k+1} (1 ≤ k ≤ N−2),
 f(t) = B_{N−1}, for A_{N−1} ≤ t < +∞.
On the other hand, Ciel cannot change her pitch instantly. So Ciel's pitch g(t) must satisfy the condition g(x) − g(y) ≤ K x − y for all real x and y. In particular g(t) is a continuous function and g'(t) ≤ K for all t where g'(t) exists (g'(t) denotes the derivative of g(t)).
The score assigned to Ciel by the karaoke machine is the value of the integral of f(t) − g(t) over the interval (−∞, +∞). Your task is to calculate the minimum value of this integral over all possible functions g(t) that satisfy the above condition.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of exactly 3 lines. The first line of each test case contains two space separated integers N and K. The second line contains N−1 space separated integers A_{1}, A_{2}, ..., A_{N−1}. Finally, the third line contains N space separated integers B_{0}, B_{1}, ..., B_{N−1}.
Output
For each test case, output a single line containing the minimum value of the integral mentioned in the problem statement. The output must have an absolute or relative error at most 0.000001 (10^{−6}). Please, note that your output should not have more than 1000 digits after the decimal point, otherwise you may (or may not) get wrong answer or runtime error (SIGXFSZ).
Constraints
 1 ≤ T ≤ 250
 2 ≤ N ≤ 8
 1 ≤ K ≤ 4
 0 ≤ A_{1} < A_{2} < ... < A_{N−1} ≤ 20130120
 0 ≤ B_{0}, B_{1}, ..., B_{N−1} ≤ 20130120
 It can occur that B_{i−1} = B_{i} for some i = 1, 2, ..., N−1
 The sum of N^{3} in one test file does not exceed 2013
Example
Input: 3 2 1 1000 900 1000 2 2 1000 900 1000 3 1 500 1200 20 60 30 Output: 2500.0000000000 1250.0000000000 625.0000000000
Explanation
The following figure corresponds to the example case 1. Here the bold red line denotes the correct pitch f(t) and the blue line denotes the optimal Ciel's pitch g(t). The answer is the area of the green region.
Author:  laycurse 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/CIELKARA 
Tags  cook30, laycurse, math, mediumhard 
Date Added:  2012013 
Time Limit:  2.013 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 