TopCoder

User's AC Ratio

56.2% (9/16)

Submission's AC Ratio

17.3% (14/81)

Description

Jolin 是個愛唱歌的小孩,每次總喜歡邊唱邊用電腦把自己的歌聲錄下來,因此長久下來,在她的電腦裡,已儲存了為數不小的個人歌唱作品。由於耶誕節快要到了,為了準備一份特別的耶誕禮物給爸爸,Jolin 準備從電腦中儲存的個人歌唱作品,挑選幾首歌製成一張個人專輯CD。由於每張CD 的容量有限,而Jolin 的個人歌唱作品早已遠遠超過一張CD 可收錄的容量,因此Jolin 希望你可以幫她想辦法,讓她所製作的專輯中,能有數目最多的歌曲(請注意:每一首歌只能被收錄一次),同時必需剛好裝滿整張CD,不留下任何未使用的空間。

Input Format

第一行為一個正整數N,代表Jolin 的個人歌唱作品數目。

第二行則有N個以空白相間隔的正整數Xi,分別代表第i 首個人歌唱作品的大小(單位為MBytes)。

第三行則有一個正整數S,代表CD 的容量(單位為MBytes)。

為簡化計算過程起見,我們假設每一首歌唱作品的大小皆不相同,同時N≦100,Xi≦200,S≦10000。

Output Format

請根據輸入的資料,輸出依序印出兩個正整數L 與K。

其中,L 代表最多可以在CD 中收錄的歌曲數目,K 代表共有幾種方式可以收錄L 首歌曲於CD 中。

注意,若歌曲曲目相同,但排列順序不同,仍視為不同的收錄方式。若沒有任何方法可以錄滿整片CD,則L=K=0。

Sample Input

輸入範例 1
5
10 50 30 70 60
80

輸入範例 2
5
10 50 30 70 60
20

Sample Output

輸出範例 1
2 4

輸出範例 2
0 0

Hints

Problem Source

原TIOJ1475 / 96北市賽
建中校內培訓第五次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

For Testdata: 0 ~ 0, Score: 14
For Testdata: 1 ~ 1, Score: 14
For Testdata: 2 ~ 2, Score: 14
For Testdata: 3 ~ 3, Score: 14
For Testdata: 4 ~ 4, Score: 14
For Testdata: 5 ~ 5, Score: 14
For Testdata: 6 ~ 6, Score: 16
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536
1 3000 65536
2 3000 65536
3 3000 65536
4 3000 65536
5 3000 65536
6 3000 65536