阿福是一名經(jīng)驗(yàn)豐富的大盜。趁著月黑風(fēng)高，阿福打算今晚洗劫一條街上的店鋪。
這條街上一共有 N 家店鋪，每家店中都有一些現(xiàn)金。阿福事先調(diào)查得知，只有當(dāng)他同時(shí)洗劫了兩家相鄰的店鋪時(shí)，街上的報(bào)警系統(tǒng)才會(huì)啟動(dòng)，然后警察就會(huì)蜂擁而至。
作為一向謹(jǐn)慎作案的大盜，阿福不愿意冒著被警察追捕的風(fēng)險(xiǎn)行竊。他想知道，在不驚動(dòng)警察的情況下，他今晚最多可以得到多少現(xiàn)金？

輸入的第一行是一個(gè)整數(shù)T(T≤50) ，表示一共有T組數(shù)據(jù)。
接下來(lái)的每組數(shù)據(jù)，第一行是一個(gè)整數(shù)N(1≤N≤100,000) ，表示一共有N家店鋪。第二行是N個(gè)被空格分開(kāi)的正整數(shù)，表示每一家店鋪中的現(xiàn)金數(shù)量。每家店鋪中的現(xiàn)金數(shù)量均不超過(guò)1000。

對(duì)于每組數(shù)據(jù)，輸出一行。該行包含一個(gè)整數(shù)，表示阿福在不驚動(dòng)警察的情況下可以得到的現(xiàn)金數(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ǔ)