Cho trước bốn số tự nhiên ~a, b, k, p~. Xét dãy số có dạng: $$~n + k,n + k + k,n + k + k + k,n + k + k + k + k,...~$$

Biết rằng ~n~ là số nhỏ nhất chia hết cho cả ~a~ và ~b~. Em hãy tính tổng các chữ số của số hạng thứ ~p~ trong dãy số trên.

Input

• Bốn số tự nhiên ~a, b, k, p~ mỗi số trên một dòng ~(1 \le a, b \le 10^8, 1 \le k \le 10, 1 \le p \le 10^7)~.

Output:

• Một số tự nhiên là kết quả của bài toán.

Sample Input

2
3
4
5

Sample Output

8

Note

Số ~6~ là số nhỏ nhất chia hết cho cả ~2~ và ~3~, nên ta có dãy số: ~10,14,18,22,26,30,...~, số ở vị trí thứ ~5~ của dãy số là ~26~. Vậy kết quả là: ~2 + 6 = 8~.