Get Minimum Cost

In category i, the j-th item costs a[i]+(j−1)b[i], and every category has infinitely many items. Buy exactly m items and minimize the total price.

输入格式

The first line contains n m, followed by one line of n values a and one line of n values b. The original bounds are 1≤n,m≤100000, 1≤a[i],b[i]≤100000.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 4
2 1 1
1 2 3

输出：

7

样例 2

输入：

1 3
5
2

输出：

21

样例 3

输入：

2 3
1 2
100 1

输出：

6

样例说明

The outputs of the three public examples are 7; 21; and 6, checked by independent enumeration or direct simulation.