#P12966. [CCO 2025] Asteroid Mining

    ID: 12768 Type: RemoteJudge 3000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>动态规划 DP贪心2025CCO(加拿大)

[CCO 2025] Asteroid Mining

题目描述

It is the year 2017 and Ryan is an asteroid miner. He makes a living by mining asteroids and selling them at the CCO (Celestial Cargo Outpost).

On his latest mining expedition, he has mined NN mineral chunks where the ii-th chunk has a value viv_i and a mass mim_i. Ryan plans to transport a set of chunks to the CCO with his rocket, but he only has enough fuel to last one more trip. He calculated that the maximum total mass he can safely carry on his rocket is MM. Due to Ryan's mining technique, the chunks exhibit a special property: for any two mineral chunks, one's mass is divisible by the other chunk's mass.

Help Ryan find the maximum total value he can ship to CCO while adhering to his rocket's constraints.

输入格式

The first line will contain two space-separated integers NN (1N5000001 \leq N \leq 500000) and MM (1M10121 \leq M \leq 10^{12}).

The next NN lines will each contain two space-separated integers viv_i (1vi10121 \leq v_i \leq 10^{12}) and mim_i (1mi10121 \leq m_i \leq 10^{12}), representing the value and mass of the ii-th mineral chunk respectively. Additionally, for any two mineral chunks i,ji, j (1i,jN1 \leq i, j \leq N), either mimjm_i \mid m_j or mjmim_j \mid m_i, where aba \mid b means that aa is a divisor of bb (i.e., ba\frac{b}{a} is an integer).

输出格式

On one line, output one integer, the maximum total value Ryan can ship to CCO.

6 10 
1 1
5 2
200 6
9 2
6 2
100 1
310

提示

Sample Explanation

Ryan can take all the chucks except the second and fifth chucks to achieve a total value of 1+200+9+100=3101 + 200 + 9 + 100 = 310. Note that the total mass of the chunks is 1+6+2+1=101 + 6 + 2 + 1 = 10. We can show that this is optimal.

The following table shows how the available 2525 marks are distributed:

Marks Awarded Bounds on NN Bounds on MM Additional Constraints
2 marks N=2N = 2 1M1041 \leq M \leq 10^4 None
1N201 \leq N \leq 20
4 marks 1N10001 \leq N \leq 1000
6 marks 1M1081 \leq M \leq 10^8
2 marks 1N5000001 \leq N \leq 500000 All mim_i are equal.
3 marks At most 2 distinct mim_i.
6 marks 1M10121 \leq M \leq 10^{12} None