CF1728F Fishermen

There are $ n $ fishermen who have just returned from a fishing trip. The $ i $ -th fisherman has caught a fish of size $ a_i $ . The fishermen will choose some order in which they are going to tell the size of the fish they caught (the order is just a permutation of size $ n $ ). However, they are not entirely honest, and they may "increase" the size of the fish they have caught. Formally, suppose the chosen order of the fishermen is $ [p_1, p_2, p_3, \dots, p_n] $ . Let $ b_i $ be the value which the $ i $ -th fisherman in the order will tell to the other fishermen. The values $ b_i $ are chosen as follows: - the first fisherman in the order just honestly tells the actual size of the fish he has caught, so $ b_1 = a_{p_1} $ ; - every other fisherman wants to tell a value that is strictly greater than the value told by the previous fisherman, and is divisible by the size of the fish that the fisherman has caught. So, for $ i > 1 $ , $ b_i $ is the smallest integer that is both strictly greater than $ b_{i-1} $ and divisible by $ a_{p_i} $ . For example, let $ n = 7 $ , $ a = [1, 8, 2, 3, 2, 2, 3] $ . If the chosen order is $ p = [1, 6, 7, 5, 3, 2, 4] $ , then: - $ b_1 = a_{p_1} = 1 $ ; - $ b_2 $ is the smallest integer divisible by $ 2 $ and greater than $ 1 $ , which is $ 2 $ ; - $ b_3 $ is the smallest integer divisible by $ 3 $ and greater than $ 2 $ , which is $ 3 $ ; - $ b_4 $ is the smallest integer divisible by $ 2 $ and greater than $ 3 $ , which is $ 4 $ ; - $ b_5 $ is the smallest integer divisible by $ 2 $ and greater than $ 4 $ , which is $ 6 $ ; - $ b_6 $ is the smallest integer divisible by $ 8 $ and greater than $ 6 $ , which is $ 8 $ ; - $ b_7 $ is the smallest integer divisible by $ 3 $ and greater than $ 8 $ , which is $ 9 $ . You have to choose the order of fishermen in a way that yields the minimum possible $ \sum\limits_{i=1}^{n} b_i $ .

N/A

N/A