TopCoder

User's AC Ratio

88.9% (16/18)

Submission's AC Ratio

28.8% (23/80)

Description

傳說中在ABCLS國中有有一個十分喜歡吃橘子的烏龜──甦蹦。

有一天當他在看橘子權威DBTF所寫的書時他讀到這樣的一段:
(T$#K(@#*$)#!+#%!+^_&%+U%JTF#(TD$T_*Y_%T*YV_HMX<FCNI

讀到之後甦蹦受到極大的啟發──原來同一顆橘子放在不同的順序吃也會有不同的飽足感!
為此他特地拿了n顆從烏龜王國空運來的橘子去請教DBTF,到底該用什麼順序吃。

經過九九八十一天的分析,DBTF成功的分析出了每顆橘子放在每個順位吃時的飽足感,
但現在問題來了,由於橘子實在太多了,DBTF無法規劃出一個優良的順序使得飽足感盡量大。
幸好甦蹦是一個很和善的人,他跟DBTF表示,只要飽足感的總和大於等於k就好了!

在問題變簡單之後,DBTF發現......他還是不會作。
但如果不交出任何結果,實在有礙於DBTF橘子權威的威名,
所以他找上了烏龜王國中曾經解出鍊金術之謎的名人,沒錯,那個人就是你。
DBTF提供了一小筆經費讓你開發程式,解出這個難題。

但身為海鞘的朋友,你自然也是視財如命,看到錢這麼少自然不高興。
在內心經過一番天人交戰以後,你決定只告訴DBTF當橘子一定要從小顆吃到大顆時至少需要吃幾顆。

現在DBTF已經把所有橘子的資訊,還有k是多少告訴你了,你能否成功的回答他呢?

Input Format

第一行有兩個數字分別代表n, k
第二行有n個數字分別代表這些橘子的大小。
接下來有n行,第 i 行的第 j 個數字 Aij 代表第 i 顆橘子放到第 j 顆吃時的飽足感。

Output Format

請輸出一個數字代表當橘子一定要從小顆吃到大顆時至少需要吃幾顆。
如果發現沒辦法達到k的話請輸出-1。

Sample Input

5 19
1 2 3 4 5
1 1 1 1 1
1 2 2 2 2
1 3 5 5 5
1 4 9 9 9
1 5 14 23 23

Sample Output

3

Hints

對於 40% 的測資 1 <= n <= 500
100% 的測資 1 <= n <= 2000
100% 1 <= k <= 106, -1000 <= Aij <= 1000

保證每顆橘子大小不一樣。

Problem Source

原TIOJ1704 / 建國中學99年校內培訓contest #add prob 2
problem setter:worm

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB)
0 10000 65536
1 10000 65536
2 10000 65536
3 10000 65536
4 10000 65536