1323 . 工廠疑雲 Products
TopCoder
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 1
10 5 8
1 0 1
1 1 0
0 0 1
1 1 0
1 2 3 4
Sample Output 1
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 |