Farmer John 有稱牛天平和 $N$ ($1 \le N \le 1000$) 個已知質量砝碼(均 31 位容納),用在一側。牛放一側,砝碼另側直到平衡。不能同側,牛有機會就踢砝碼到他臉上。一側總質量超 $C$ ($1 \le C < 2^{30}$) 會壞。
砝碼由小至大,第三個起每個至少前兩個之和。
求砝碼可精確量的最大質量,總量不大於 $C$,可能不能全放。
寫程式由列表及天平承受上限求合法精確稱量最大值。
輸入格式
第 1 列:空格分隔正整數 $N$、$C$。
第 $2..N+1$ 列:每列一正整數砝碼質量,保證非遞減。
輸出格式
第 1 列:一整數,最大準確安全測量質量。
範例
輸入格式 1
3 15 1 10 20
輸出格式 1
11
說明
三砝碼 1、10、20,一側上限 15。
用 1 和 10 量 11,任何可組更大值皆弄壞。