TopCoder

Thumb agd logo info 1024x686
$\mathbb{R}$
$\Huge\mathfrak{AC}\circlearrowleft$

User's AC Ratio

100.0% (37/37)

Submission's AC Ratio

66.7% (56/84)

Description

抓寶桌遊打算在市區開N 家連鎖店。可以開連鎖店的位置是M x M 的網格,每一家連鎖店必須開在不同的網格上,而且第二家連鎖店必須開在第一家的東北方,第三家連鎖店必須開在第二家的東北方,依此類推。東北方的定義爲X 座標和Y 座標都比較大。X 座標和Y 座標均介於0 到 M - 1。如果第 i 家 (i 介於0 到 N - 1)連鎖店開在 (x, y) 的位置則會有 ((ai + bx + cy) mod d) 的顧客。請寫一個程式決定N 家連鎖店的位置,使得所有連鎖店的顧客數總和為最大。

Input Format

輸入爲一行六個正整數:M N a b c d,1 ≤ a, b, c ≤ 2,000,1 ≤ d ≤ 1,200,000,兩整數間皆有一個空白。

Output Format

輸出爲一整數,代表所有連鎖店的顧客數總和的最大值。

Sample Input

4 2 1 2 3 17

Sample Output

26

Hints

本題共有兩個子題,每一子題可有多筆測試資料:
第一子題的測試資料 1 ≤ M ≤ 20,1 ≤ N ≤ 10 ,全部解出可獲37 分
第二子題的測試資料 1 ≤ M ≤ 200,1 ≤ N ≤ 100,全部解出可獲63 分

Problem Source

105學年度高級中學資訊學科能力競賽決賽 程式設計試題第一題

Subtasks

For Testdata: 0 ~ 0, Score: 37
For Testdata: 1 ~ 1, Score: 63
No. Time Limit (ms) Memory Limit (KiB)
0 1000 524288
1 1000 524288