某天KID利用飛行器飛到了一個(gè)金銀島上，上面有許多珍貴的金屬，KID雖然更喜歡各種寶石的藝術(shù)品，可是也不拒絕這樣珍貴的金屬。但是他只帶著一個(gè)口袋，口袋至多只能裝重量為w的物品。島上金屬有s個(gè)種類, 每種金屬重量不同，分別為n1,n2,...,ns，同時(shí)每個(gè)種類的金屬總的價(jià)值也不同，分別為v1,v2,...,vs。KID想一次帶走價(jià)值盡可能多的金屬，問他最多能帶走價(jià)值多少的金屬。注意到金屬是可以被任意分割的，并且金屬的價(jià)值和其重量成正比。

第1行是測試數(shù)據(jù)的組數(shù)kk，后面跟著kk組輸入。
每組測試數(shù)據(jù)占3行，第1行是一個(gè)正整數(shù)w(1≤w≤10000)，表示口袋承重上限。第2行是一個(gè)正整數(shù)s(1≤s≤100)，表示金屬種類。第3行有2s個(gè)正整數(shù)，分別為n1,v1,n2,v2,...,ns,vs分別為第一種，第二種，...，第s種金屬的總重量和總價(jià)值(1≤ni≤10000,1≤vi≤10000)。

k行，每行輸出對應(yīng)一個(gè)輸入。輸出應(yīng)精確到小數(shù)點(diǎn)后2位。

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

編程練習(xí) 貪心 基礎(chǔ)