TopCoder

Caido
主唱太拼命了

User's AC Ratio

70.0% (7/10)

Submission's AC Ratio

35.0% (7/20)

Tags

Description

老陳想來開一家店,但根據當地神奇的法規,正職員工和約聘員工的人數有以下限制:令正職員工有 x 人,約聘員工有 y 人,x,y 需滿足以下三條關係式:
1. a1x+b1yc1
2. a2x+b2yc2
3. a3x+b3yc3

並且沒辦法聘超過 1000 個正職員工或超過 1000 個約聘員工。
每位正職員工能帶來 ux 的產值,每位約聘員工能帶來 uy 的產值,請幫他計算最高能有多少的產值。

Input Format

第一行有兩個數字 ux,uy
接下來三行每行有三個數字 ai,bi,ci

  • 1ux,uy1000
  • 0ai,bi,ci1000 i

Output Format

最高能達到多少的產值,如果他沒辦法聘用任何員工,請輸出 0

Sample Input 1

2 3
1 0 10
0 1 10
1 1 15

Sample Output 1

40

Sample Input 2

1 1
1 2 100
2 1 100
1 0 30

Sample Output 2

65

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2