Masala F

Azimjon kunlardan bir kuni g'alati bir orolga tushib qoldi. Bu oroldagi $K$ ta daraxt mavjud. Bu daraxtning o'ziga hos hususiyati daraxt aylana shaklida bo'lib, uning har bir tugunida pullar o'sar edi. Ammo, hamma yerda bo'lgani kabi bu yerni ham o'zining aholisi va qiroli bor edi. Shuning uchun Azimjon shunchaki hamma pullarni terib olib keta olmas edi. Yaxshiyamki qirol sahiy va uning mehmonlarga nisbatan hurmati baland ekan. U Azimjonga istalgan faqat bitta daraxtni tanlashni va u ustida bitta o'yin o'ynashni taklif qildi, o'yin qoidalari quyidagicha: dastlab Azimjon o'zi uchun istalgan bir tugunni tanlaydi va undagi pulni oladi. So'ng, qirol ham o'zi uchun bir tugunni tanlab undagi pulni o'z haznasiga qoshib qo'yadi. Ikkala holatda ham tugundagi pullar qiymati $0$ ga teng bo'lib qoladi. Keyingi har bir qadamda, azimjon oldin pul olgan tugunlar bilan bog'langan biror qiymati $0$ ga teng bo'lmagan tugunni tanlaydi va undagi pulni oladi. Qirol ham har bir qadamda ilgari pul olgan tugunlar bilan bog'langan istalgan qiymati $0$ ga teng bo'lmagan tugunni tanlab undagi pulni o'ziga oladi(Ikkala o'yinchi ham navbati kelganda yurish qila olmasa shunchaki navbatini o'tkizib yuboraveradi). Azimjon boshqa pul ololmay qolgan payt o'yinni yakunlaydi. Qirolning xazinasida pul ko'p bo'lgani sababli unga u qancha pul yig'ishi muhim emas, u faqat Azimjon olishi mumkin bo'lgan pulni minimallashtirishni hohlaydi. Albatta Azimjon esa bu daraxtni tanlaganda boshqa daraxtni tanlagandagidan ko'ra ko'proq pul yutishni hohlaydi.  Ikkala o'yinchi ham optimal o'ynasa Azimjon olishi mumkin bo'lgan maksimum pul miqdorini toping.   

Dastlabki qatorda $K(1 \leq K \leq 30)$ daraxtlar soni kiritiladi. 
Keyingi $K$ ta qatorda dastlab $N(1 \leq N \leq 10^4)$soni so'ng yangi qatorda $N$ ta elementdan tashkil topgan $A(1 \leq A_i \leq 2000)$ massivi ko'rinishida aylana shaklidagi daraxt kiritiladi. Bunda barcha ketma-ket elementlar bog'langan shu bilan birga,  $1$ chi va $N$ chi elementlar ham.  
 

Azimjon olishi mumkin bo'lgan maksimal pulning miqdorini toping.