信息學(xué)院的同學(xué)小明畢業(yè)之后打算創(chuàng)業(yè)開(kāi)餐館.現(xiàn)在共有n個(gè)地點(diǎn)可供選擇。小明打算從中選擇合適的位置開(kāi)設(shè)一些餐館。這n個(gè)地點(diǎn)排列在同一條直線上。我們用一個(gè)整數(shù)序列m1,m2,...mn來(lái)表示他們的相對(duì)位置。由于地段關(guān)系,開(kāi)餐館的利潤(rùn)會(huì)有所不同。我們用pi表示在mi處開(kāi)餐館的利潤(rùn)。為了避免自己的餐館的內(nèi)部競(jìng)爭(zhēng),餐館之間的距離必須大于k。請(qǐng)你幫助小明選擇一個(gè)總利潤(rùn)最大的方案。

輸入第一行是整數(shù) T(1≤T≤1000)，表明有T組測(cè)試數(shù)據(jù)。緊接著有TT組連續(xù)的測(cè)試。每組測(cè)試數(shù)據(jù)有33行。
第1行:地點(diǎn)總數(shù)n(n<100), 距離限制k(k>0且k<1000)；
第2行:n 個(gè)地點(diǎn)的位置m1,m2,...mn(1000000>mi>0且為整數(shù),升序排列)；
第3行:n 個(gè)地點(diǎn)的餐館利潤(rùn)p1,p2,...pn(1000>pi>0且為整數(shù))。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

編程練習(xí) 動(dòng)態(tài)規(guī)劃 基礎(chǔ)