BOBERT  Stick values
On a sunny day, Stjepan and Bobert were arguing over their problem solving skill under a big apple tree. Bobert brought up a nice problem he had just recently solved and claimed that Stjepan could not solve it. Stjepan is desperate and needs your help. Here is Bobert's problem:
Given an array of N (1 <= N <= 10^5) numbers (0 <= ai <= 10^9) and K (1 <= K <= 20) sticks of a certain length Li (0 <= Li <= N, such that the sum of all lengths is equal to N), find the best possible distribution of the sticks among the array such that:
 a stick of length L_{x} can cover any interval of the array whose length is equal to the length of the stick (it can cover L_{x} consecutive numbers of the array).
 all sticks must be used and can not overlap or leave the borders of the array.
 the value of a stick of length L_{x} covering the interval [lo, hi] is equal to: L_{x} * (max[lo, hi]  min[lo, hi]). Note that: max = largest element of the array inside the interval and min = smallest element of the array inside the interval.
 the sum of all stick values must be as large as possible.
Note: doublecheck your complexity
Input
The first line contains an integer N.
The second line contains N numbers representing the array.
The third line contains an integer K.
The fourth line contains K numbers representing the stick lengths.
Output
The only line should contain the solution  the maximum sum of stick values as explained in the task.
Example
Input: 9 2 6 3 1 8 4 3 5 6 4 2 3 2 2 Output: 33
hide comments
nimphy:
20180519 09:17:46
cost me 10s？emmm。。。。 

californiagurl:
20150613 13:55:43
why do i keep getting SIGABRT? 

:D:
20150315 00:44:21
Very fun problem. Not too hard, but pretty interesting. Thanks Vedran for preparing it.


What Does The Fox Say?:
20150211 09:21:50
testcase contains Li = 0?


Stjepan Pozgaj:
20150211 09:21:50
very nice problem! 
Added by:  Vedran Kurdija 
Date:  20150108 
Time limit:  1s2.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  own problem 