Yêu cầu: Nhập vào số tự nhiên \(n\), vẽ hình bậc \(n\).

Chấm điểm:

• Vẽ hình bậc 2 được 50 điểm
• Nhập \(n, (1 \le n \le 10)\), vẽ được cây thông có \(n\) cành tương ứng được 35 điểm
• Canh chỉnh hình nằm giữa màn hình được 5 điểm
• Cạnh của tam giác đơn vị thay đổi dựa vào bậc của hình được 10 điểm
  • Bậc 1 có cạnh của tam giác đơn vị là \(a\) (Hình vẽ chiếm diện tích đối đa màn hình vẽ có thể)
  • Bậc 2 có cạnh của tam giác đơn vị là \(\dfrac{a}{2}\)
  • Bậc 4 có cạnh của tam giác đơn vị là \(\dfrac{a}{4}\)
  • ...
• Nếu không tô được màu trừ 40% số điểm tương ứng

Vì là lứa thí sinh nhỏ tuổi nhất trong cuộc thi nên để giúp các em học sinh tiểu học giữ được sự thoải mái trước khi làm bài, Ban tổ chức quyết định sẽ phát các cây kẹo cho \(N\) học sinh (\(N\) là số tự nhiên). Ban tổ chức muốn mỗi thí sinh sẽ nhận được \(K\) cây kẹo, và một gói kẹo bán ở cửa hàng sẽ có \(T\) cây kẹo, mỗi gói kẹo giá \(X\) ngàn đồng. Hỏi để phát đủ các cây kẹo cho các thí sinh thì ban tổ chức phải bỏ ra ít nhất bao nhiêu tiền để mua các gói kẹo?

Input

• Gồm 4 số tự nhiên \(N,K,T,X\), mỗi số có giá trị không quá \(10\,000\).

Output

• Đáp án thỏa mãn yêu cầu đề bài.

Example

10 2 4 100

500

5 3 2 5

40

Một xâu được gọi là xâu đối xứng nếu nó đọc giống nhau từ trái sang phải và từ phải sang trái. Ví dụ: \(abcba, abba, xyzzyx . . .\) là xâu đối xứng, \(abc, abab, mnnn\) không phải là xâu đối xứng.

Bạn được cho một xâu \(S\) bao gồm các chữ cái tiếng Anh viết thường. Mỗi lần biến đổi, bạn có thể chọn bất kỳ một vị trí nào trong xâu rồi thay đổi chữ cái ở vị trí đó thành bất kỳ chữ cái tiếng Anh viết thường nào khác và độ dài của xâu là không đổi. Bạn cũng có thể hoán vị thứ tự của các chữ cái trong xâu một cách tùy ý. Chú ý rằng hoán vị không được tính là một phép biến đổi.

Yêu cầu: Hãy tính số lần biến đổi tối thiểu để xâu \(S\) trở thành một xâu đối xứng. Nếu sau số lần biến đổi tối thiểu ấy có nhiều xâu \(S\) thỏa mãn, in ra xâu có thứ tự từ điển nhỏ nhất.

Input

• Nhập từ bàn phím xâu S bao gồm các chữ cái tiếng Anh viết thường.

Output

• In ra xâu đối xứng có thứ tự từ điển nhỏ nhất có thể nhận được sau số lần biến đổi tối thiểu.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \leq 10\) và chỉ có 3 loại ký tự \(a, b\) và \(c\), thí sinh sẽ được \(40\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 1000\), thí sinh sẽ được \(80\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{5}\), thí sinh sẽ được \(100\) điểm.

Example

abac

abba

abacad

aabbaa

Một số tự nhiên \(X\) được gọi là số ODD đối xứng nếu như:

• Các chữ số của \(X\) đều là số lẻ.
• \(X\) đọc từ trái sang phải cho kết quả giống như đọc từ phải sang trái.

Các số ODD đối xứng đầu tiên: \(1;3;5;7;9;11;33;55;77;99;111;131;...\)

Yêu cầu: Nhập từ bàn phím số tự nhiên \(N\). Hãy in ra số ODD đối xứng thứ \(N\).

Input

• Nhập số tự nhiên \(N\) với \(1 \le N \le 10^{16}\).

Output

• Xuất ra số ODD đối xứng thứ \(N\).

Scoring

• Có \(60\%\) test tương ứng \(60\%\) số điểm của bài với \(n < 10^6\);
• Có \(40\%\) test khác tương ứng với \(40\%\) số điểm còn lại của bài với \(n < 10^{16}\);

2

3

7

33