小Y写文章

发布时间: 2018年4月15日 23:06   最后更新: 2018年4月15日 23:25   时间限制: 2000ms   内存限制: 128M

小Y 写了一篇文章,他对自己的文笔很有自信,尤其是自己总结出了一套计算文章通顺性的公式。

文章共$N$段,对于文章的每一段小Y对它都能计算出一个估值$A_i$,而一篇文章的不连贯值定义为$\max \lbrace |A_i - A_{i-1}|; 2  \le i \le n \rbrace$,现在小Y 想要发布他的文章,但是编辑小Z 让他加入一些广告,具体来说就是M 段估值分别为B_i 的新段落。小Y 很头疼,想让修改后的文章依然通顺,也就是要最小化不连贯值,已知小Y 加入新段落的时候不需要考虑新段落之间的顺序,但是只可以在原文章的开头段之前、结尾段之后、或两段之间加入一段新段落,每个位置只能加入最多一段。请帮助焦头烂额的小Y 求出将这M 个新段落全都加入之后的最小不连贯值。

多组数据,第一行有一个正整数$T$($T \le 30$) 表示数据组数。
之后有$T$组数据,每组数据第一行有两个整数$N$;$M$。
接着有两行,其中第一行有$N$个正整数$A_i$,表示原文章按顺序每段的估值。
第二行有$M$个正整数$B_i$,表示新段落每段的估值。
$1 \le N \le 200$, $1 \le M \le N + 1$, $1 \le A_i;B_i \le 10^9$

对于每组数据,输出一个整数表示求出的最小不连贯值。

复制
2
4 3
1 6 5 2
3 1 4
4 2
1 2 4 3
10 10
3
7

第一组样例方案可以是 (1) 1 (4) 6 5 (3) 2

第二组样例方案可以是 1 2 4 (10) 3 (10)

2018

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛