719 . 阿納克的失落遺跡-1

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Yannick

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

71.4% (5/7)

Tags

apcsc apcsc-greedy

Description

有一隊考古學家到了阿納克的失落遺蹟探險，他們在遺蹟中發現了許多值錢的古代錢幣，因為該文化信奉畢達哥拉斯主義的關係，所有錢幣的重量都互相整除。他們想帶一些錢幣回去補貼探險經費，但背包的負重有限，請幫他們計算最多可以帶價值多少的錢幣回去。

Input Format

第一行有兩個整數 $N,M$，$N$ 代表找到了幾種錢幣，$M$ 代表最多能帶走多重的錢幣。
接下來 $N$ 行，每行有一個整數 $v_i,w_i$，代表第 $i$ 種錢幣的價值與重量。

  • $1 \le N \le 2 \times 10^ 5$
  • $1 \le M \le 2 \times 10^ 9$
  • $1 \le v_i,w_i \le 2 \times 10^ 9 \ \ \forall i$
  • 對於所有 $i,j$，保證 $w_i | w_j$ 或 $w_j|w_i$

Output Format

最多能帶走的價值多少的錢幣。

Sample Input 1

1 10
100 3

Sample Output 1

300

Sample Input 2

3 100
1 1
10 3
100 9

Sample Output 2

1101

Hints

Problem Source

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
Submit
Back to Top