CF812C Sagheer and Nubian Market

On his trip to Luxor and Aswan, Sagheer went to a Nubian market to buy some souvenirs for his friends and relatives. The market has some strange rules. It contains $ n $ different items numbered from $ 1 $ to $ n $ . The $ i $ -th item has base cost $ a_{i} $ Egyptian pounds. If Sagheer buys $ k $ items with indices $ x_{1},x_{2},...,x_{k} $ , then the cost of item $ x_{j} $ is $ a_{xj}+x_{j}·k $ for $ 1

N/A

N/A

In the first example, he cannot take the three items because they will cost him $ [5,9,14] $ with total cost $ 28 $ . If he decides to take only two items, then the costs will be $ [4,7,11] $ . So he can afford the first and second items. In the second example, he can buy all items as they will cost him $ [5,10,17,22] $ . In the third example, there is only one souvenir in the market which will cost him $ 8 $ pounds, so he cannot buy it.