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\).

Yêu cầu: Em hãy tính tổng các chữ số của số hạng thứ \(p\) trong dãy số trên.

Đầu vào: Bốn số tự nhiên \(a, b, k, p\) mỗi số trên một dòng \((1 ≤ a,b ≤ 10^8, 1 ≤ k ≤10, 1 ≤ p ≤ 10^7)\).

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

input

2
3
4
5

output

8

Giải thích
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\)