TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

63.2% (12/19)

Description

是的,在這個什麼都漲,只有薪水不漲的時代,連個往來南北辛苦通勤的車費也沒辦法補助。

是一個大家都想節省的年代。甚至連原物料都不太夠了。
(是的,尤其是銅礦的缺乏,你不得已增加了許多經費用於鑄造金銀製品。)

你是一位經營原料製造的公司老闆,你領導的公司,利用最原始的原料,製造出一些可以被更多工廠使用的材料。

但是,有一天,你突然發現了一件很悲慘的事情:這個月,你的工廠只剩下一點點原始原料的庫存了!

這些原料,在這個月底之前不用完的話,就必須處理掉,否則會損壞而無法使用。

工廠利用這m種原料,生產n種材料。
每生產一單位的第i種材料,你可以獲得利潤 Ci(萬元),注意即使你生產了不足一單位,也可以相同比例獲得利潤。
而庫存裡面,第j種原料的份量只剩下Rj單位了。

你手上拿著每一種材料的「配方表」,也就是說,它告訴你,生產一單位的某種材料,會需要消耗每一種原料各多少單位。

請問這個月底之前,你最多能夠獲得多少萬元的利潤呢?

Input Format

每個輸入檔只包含一筆測試資料,測試資料的第一列有兩個正整數m,n (1<= m,n <=500),分別代表原料的種數以及材料的種數。
第二列有m個整數R1, R2,..., Rm (0<=Ri<=1,000)代表每一種原料剩餘的單位數。
接下來有n列,每一列包含m個整數,第i列的第j個數代表生產一單位第i種材料需要消耗第j種原料的單位數。(這些數字很恰好地,都是0或1的整數)
最後一列包含n個整數 C1, C2,...,Cn代表生產一單位的材料分別可以獲得多少利潤。(-10,000<=Ci<=10,000)

Output Format

請輸出可能獲得的最大利潤,輸出至小數點第三位。

Sample Input

3 4
10 5 8
1 0 1
1 1 0
0 0 1
1 1 0
1 2 3 4

Sample Output

44.000

Hints

對於範例測資來說:生產 8單位的材料3,以及 5單位的材料4,可以獲得最大利潤 3*8+5*4=44,而且剛好把原料2和原料3用光。

你可以假設測資都是隨機產生的...。

Problem Source

原TIOJ1323 / TIOJ IOI Warmup III, 2008. Problemsetter: tmt514

Subtasks

No. Testdata Range Score
1 0 8
2 1 8
3 2 8
4 3 8
5 4 8
6 5 8
7 6 8
8 7 8
9 8 8
10 9 8
11 10 8
12 11 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10
10 5000 65536 262144 11
11 5000 65536 262144 12