Duff is addicted to meat! Malek wants to keep her happy for *n* days. In order to be happy in *i*-th day, she needs to eat exactly *a*_{i} kilograms of meat.

There is a big shop uptown and Malek wants to buy meat for her from there. In *i*-th day, they sell meat for *p*_{i} dollars per kilogram. Malek knows all numbers *a*_{1}, ..., *a*_{n} and *p*_{1}, ..., *p*_{n}. In each day, he can buy arbitrary amount of meat, also he can keep some meat he has for the future.

Malek is a little tired from cooking meat, so he asked for your help. Help him to minimize the total money he spends to keep Duff happy for *n* days.

提交代码