1133B.md (2095B)
1 Source: https://codeforces.com/problemset/problem/1133/B 2 3 B. Preparation for International Women's Day 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 International Women's Day is coming soon! Polycarp is preparing for the holiday. 22 23 There are $n$ candy boxes in the shop for sale. The $i$-th box contains $d_i$ candies. 24 25 Polycarp wants to prepare the maximum number of gifts for $k$ girls. Each gift will consist of exactly two boxes. The girls should be able to share each gift equally, so the total amount of candies in a gift (in a pair of boxes) should be divisible by $k$. In other words, two boxes $i$ and $j$ ($i \ne j$) can be combined as a gift if $d_i + d_j$ is divisible by $k$. 26 27 How many boxes will Polycarp be able to give? Of course, each box can be a part of no more than one gift. Polycarp cannot use boxes "partially" or redistribute candies between them. 28 29 Input 30 31 The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 100$) — the number the boxes and the number the girls. 32 33 The second line of the input contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$), where $d_i$ is the number of candies in the $i$-th box. 34 35 Output 36 37 Print one integer — the maximum number of the boxes Polycarp can give as gifts. 38 39 Examples 40 41 Input 42 43 ``` 44 7 2 45 1 2 2 3 2 4 10 46 ``` 47 48 Output 49 50 ``` 51 6 52 ``` 53 54 Input 55 56 ``` 57 8 2 58 1 2 2 3 2 4 6 10 59 ``` 60 61 Output 62 63 ``` 64 8 65 ``` 66 67 Input 68 69 ``` 70 7 3 71 1 2 2 3 2 4 5 72 ``` 73 74 Output 75 76 ``` 77 4 78 ``` 79 80 Note 81 82 In the first example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes): 83 84 * $(2, 3)$; 85 * $(5, 6)$; 86 * $(1, 4)$. 87 88 So the answer is $6$. 89 90 In the second example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes): 91 92 * $(6, 8)$; 93 * $(2, 3)$; 94 * $(1, 4)$; 95 * $(5, 7)$. 96 97 So the answer is $8$. 98 99 In the third example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes): 100 101 * $(1, 2)$; 102 * $(6, 7)$. 103 104 So the answer is $4$.