Trên một con đường có \(n\) lô đất, mỗi lô sẽ được xây một tòa nhà, đánh số từ \(1\) đến \(n\) từ trái sang phải.
Chính quyền muốn xây một tòa nhà chọc trời tại vị trí \(k\) với độ cao \(h\) tầng.
Các tòa nhà còn lại cần được xây với độ cao thấp nhất có thể, sao cho:

• Mỗi tòa nhà có ít nhất 1 tầng.
• Hai tòa nhà liền kề có độ chênh lệch không quá \(d\) tầng.
• Vẫn phải đảm bảo tòa nhà thứ \(k\) cao đúng \(h\) tầng.

Yêu cầu

Tính tổng số tầng tối thiểu cần xây cho cả \(n\) tòa nhà.

Input

• Gồm 4 dòng, mỗi dòng là một số nguyên dương:
  • Dòng 1: \(n\) – số tòa nhà (\(1 \leq n \leq 10^7\))
  • Dòng 2: \(k\) – vị trí tòa nhà chọc trời (\(1 \leq k \leq n\))
  • Dòng 3: \(h\) – chiều cao của tòa nhà thứ \(k\) (\(1 \leq h \leq 10^8\))
  • Dòng 4: \(d\) – chênh lệch tối đa giữa 2 nhà liền kề (\(1 \leq d < h\))

Output

• Một dòng duy nhất ghi tổng số tầng tối thiểu cần xây cho \(n\) tòa nhà.

Example

6
2
3
1

10

  █ 
█ █ █
█ █ █ █ █ █
1 2 3 4 5 6

5
3
6
2

18

Scoring

• Subtask \(1\) (\(30\) điểm): \(n \leq 100\).
• Subtask \(2\) (\(30\) điểm): \(d = 1\).
• Subtask \(3\) (\(40\) điểm): Không giới hạn gì thêm.