CF175C Geometry Horse

Vasya plays the Geometry Horse. The game goal is to destroy geometric figures of the game world. A certain number of points is given for destroying each figure depending on the figure type and the current factor value. There are $ n $ types of geometric figures. The number of figures of type $ k_{i} $ and figure cost $ c_{i} $ is known for each figure type. A player gets $ c_{i}·f $ points for destroying one figure of type $ i $ , where $ f $ is the current factor. The factor value can be an integer number from $ 1 $ to $ t+1 $ , inclusive. At the beginning of the game the factor value is equal to 1. The factor is set to $ i+1 $ after destruction of $ p_{i} $ $ (1

The first line contains the only integer number $ n $ $ (1

Print the only number — the maximum number of points Vasya can get.

In the first example Vasya destroys three figures first and gets $ 3·1·10=30 $ points. Then the factor will become equal to $ 2 $ and after destroying the last two figures Vasya will get $ 2·2·10=40 $ points. As a result Vasya will get $ 70 $ points. In the second example all $ 8 $ figures will be destroyed with factor $ 1 $ , so Vasya will get $ (3·8+5·10)·1=74 $ points.