Vào một ngày đẹp trời, mẹ nhờ Long đi mua một giỏ táo gồm ~k~ quả để mang đi tặng bà của bạn ấy. Khi đến cửa hàng trái cây, Long được giới thiệu đến ~2~ loại táo ngon nhất hiện nay và đều chất lượng như nhau:

• Loại 1: Táo đỏ nhập khẩu từ New Zealand.
• Loại 2: Táo xanh Việt Nam chất lượng cao.

Với cách bán mỗi loại như sau:

• Loại 1 có giá ~a~ đồng.
• Loại 2 đang trong chương trình khuyến mãi vô cùng đặc biệt. Bởi Vạn là người vô cùng yêu thích sử dụng hàng Việt Nam nên anh ấy đã đặt ra chương trình khuyến mãi là: mua ~2~ quả tính tiền ~1~ quả và giá mỗi quả táo là ~b~ đồng (không bán ~1~ quả lẻ).

Bởi chất lượng ~2~ loại táo là như nhau nên hãy giúp Long tính được số tiền ít nhất cần phải trả để mua đúng ~k~ quả táo.

Dữ liệu

• Dòng đầu tiên chứa số tự nhiên ~a~ ~(1 ≤ a ≤ 10^9)~.
• Dòng thứ hai chứa số tự nhiên ~b~ ~(1 ≤ b ≤ 10^9)~.
• Dòng thứ ba chứa số tự nhiên ~k~ ~(1 ≤ k ≤ 10^9)~.

Kết quả

• In ra một số tự nhiên duy nhất là số tiền ít nhất cần phải trả để mua đúng ~k~ quả táo.

Sample Input 1

15
5
2005

Sample Output 1

5025

Sample Input 2

5
9
2005

Sample Output 2

9023

Xâu đối xứng là xâu đọc từ trái qua phải giống như xâu đọc từ phải qua trái.

Ví dụ: Các xâu ABA, ABCCBA là các xâu đối xứng.

Bạn có được phép thuật lấy một ký tự bất kỳ để biến đổi thành một ký tự khác và cho phép sắp xếp thứ tự các ký tự trong xâu.

Ví dụ: Cho xâu ~S=~ ABCB có thể biến đổi thành xâu ~S=~ ABAB và có thể sắp xếp thành xâu ~S=~ ABBA. Xâu cuối cùng nhận được là xâu đối xứng.

Yêu cầu: Cho xâu ~S~ chỉ gồm ba ký tự A, B, C, hãy tính số lần thực hiện phép thuật ít nhất để biến đổi ~S~ thành xâu đối xứng.

Dữ liệu

• Một xâu ký tự ~S~ chỉ gồm ba ký tự A, B, C có độ dài không quá ~1000~ ký tự.

Kết quả

• In ra một số tự nhiên là kết quả bài toán.

Sample Input 1

CCB

Sample Output 1

0

Note

Không cần biến đổi. Chỉ cần sắp xếp thứ tự các ký tự thành xâu CBC đối xứng.

Sample Input 2

AAABBCB

Sample Output 2

1

Note

Có thể biến đổi ký tự C thành ký tự A được xâu AAABBAB. Sau đó sắp xếp thứ tự thành xâu AABBBAA là xâu đối xứng.

Cho ba số tự nhiên ~a~, ~n~, ~k~. Từ ba số đó tạo thành dãy số có dạng

$$~a~, ~a + k~, ~a + k + k~, ~a + k + k + k~, ~…~, ~a+(n-1)×k~$$

(số sau lớn hơn số ngay trước nó ~k~ đơn vị).

Ví dụ: ~a=1,n=5,k=3~ thì dãy số trở thành ~1,4,7,10,13~.

Cho ba số tự nhiên ~a~, ~n~, ~k~, hãy tính tổng ~n~ số hạng của dãy số tạo được theo cách trên.

Dữ liệu

• Dòng đầu tiên chứa số tự nhiên ~a~ ~(1 ≤ a ≤1000)~.
• Dòng thứ hai chứa số tự nhiên ~n~ ~(1 ≤ n ≤ 10^7)~.
• Dòng thứ ba chứa số tự nhiên ~k~ ~(1 ≤ k ≤ 1000)~.

Kết quả

• Một số tự nhiên duy nhất là tổng ~n~ số hạng đầu tiên của dãy số.

Sample Input 1

1
2
3

Sample Output 1

5

Note

Dãy số được tạo ra ~1, 4~ nên tổng của nó là ~5~

Sample Input 2

5
5
5

Sample Output 2

75

Note

Dãy số được tạo ra ~5,10,15,20,25~ nên tổng của nó là ~75~.