APCS201810第4題置物櫃出租

王老先生有一個置物櫃，共有 M 個相同大小的格子，置物櫃目前已經租給 n 個客戶，第 i 位客戶所租的大小為 f(i) 個格子 (1≤i≤n) 。目前的承租量總和不超過 M ，但是現在王老先生自己需要使用 S 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。

假設每個客戶所租容量只能全退或全不退，而退租第 i 個客戶損失的利益與其所租容量 f(i) 相同，請寫一支程式計算王老先生最小的損失利益，如果不須退租，則損失為 0 。

輸入說明

測試資料有兩行，第一行有三個正整數，依序是 n 、 M 與 S ，其中 S<=M ，第二行是 n 個正整數 f(1) , f(2) , f(3) , ... , f(n) ，同一行的數字間以空白隔開，此行的最後有一個空格， 1≤n≤100，M≤2e5。

輸出說明

輸出王老先生最小的損失利益。

輸入範例1

3 10 6

4 4 1

輸出範例1

輸入範例2

5 20 14

8 2 7 2 1

輸出範例2

解題策略

模擬，集合