No.3502 GCD Knapsack
タグ : / 解いたユーザー数 100
作問者 :
Naru820
/ テスター :
Nzt3
irinoirino
Solalyth
Problem Statement
There are $N$ items. The $i$-th item has weight $X_i$ and value $Y_i$.
Determine whether it is possible to choose $1$ or more items so that the greatest common divisor of the weights of the chosen items is at least $W$. If it is possible, find the maximum possible sum of the values of the chosen items.
Constraints
- $1 \leq N,W \leq 2 \times 10^5$
- $1 \le X_i \le 2\times 10^5$
- $1 \le Y_i \le 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$N \ W$ $X_1 \ X_2 \ldots X_N$ $Y_1 \ Y_2 \ldots Y_N$
Output
If it is not possible to choose items, print $0$. Otherwise, print the maximum possible sum of the values of the items.
Sample
Sample 1
Input
3 2 4 2 3 5 2 8
Output
8
The ways to choose items such that the greatest common divisor of the weights is at least $2$ are as follows.
- Choose item $1$. The total value is $5$.
- Choose item $2$. The total value is $2$.
- Choose item $3$. The total value is $8$.
- Choose items $1,2$. The total value is $7$.
Therefore, the maximum total value is $8$, so the answer is $8$.
Sample 2
Input
5 10 4 6 2 3 9 5 8 2 4 6
Output
0
It is not possible to choose items so that the greatest common divisor of the weights is at least $10$. Therefore, print $0$.
Sample 3
Input
20 26 6736 1887 1758 918 1150 1210 1975 958 763 1784 224 25 1794 15 963 1314 615 1526 7301 680 752 18717 225699 70 6427 314 61610 587 343 10924 1250 290 64100 5315 8566 84972 4135 2946 11 40640
Output
225699
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。