CF1367E Necklace Assembly

The store sells $ n $ beads. The color of each bead is described by a lowercase letter of the English alphabet ("a"–"z"). You want to buy some beads to assemble a necklace from them. A necklace is a set of beads connected in a circle. For example, if the store sells beads "a", "b", "c", "a", "c", "c", then you can assemble the following necklaces (these are not all possible options): And the following necklaces cannot be assembled from beads sold in the store: The first necklace cannot be assembled because it has three beads "a" (of the two available). The second necklace cannot be assembled because it contains a bead "d", which is not sold in the store.We call a necklace $ k $ -beautiful if, when it is turned clockwise by $ k $ beads, the necklace remains unchanged. For example, here is a sequence of three turns of a necklace.  As you can see, this necklace is, for example, $ 3 $ -beautiful, $ 6 $ -beautiful, $ 9 $ -beautiful, and so on, but it is not $ 1 $ -beautiful or $ 2 $ -beautiful.In particular, a necklace of length $ 1 $ is $ k $ -beautiful for any integer $ k $ . A necklace that consists of beads of the same color is also beautiful for any $ k $ . You are given the integers $ n $ and $ k $ , and also the string $ s $ containing $ n $ lowercase letters of the English alphabet — each letter defines a bead in the store. You can buy any subset of beads and connect them in any order. Find the maximum length of a $ k $ -beautiful necklace you can assemble.

N/A

N/A

The first test case is explained in the statement. In the second test case, a $ 6 $ -beautiful necklace can be assembled from all the letters. In the third test case, a $ 1000 $ -beautiful necklace can be assembled, for example, from beads "abzyo".