Contest ôn tập THT bảng A - 2023 #03

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; \dots\)

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

Example

2

3

7

33

Scoring

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