maxcoin

Phần chơi giành cho khán giả giữa một chương trình truyền hình có nội dung như sau:

• Một khán giả được chọn làm người chơi và được tặng n đồng. 
• Nếu n chẵn thì người chơi phải đưa cho người dẫn chương trình một nữa số tiền mình có, trong trường hợp ngược lại người chơi nhận được thêm 2n+1 đồng.
• Sau mỗi lần, người chơi quyết định có tiếp tục chơi hay dừng trò chơi.
• Trò chơi cũng kết thúc khi người chơi chỉ còn 1 đồng.

Hãy xác định số tiền lớn nhất người chơi có thể nhận được nếu biết cách dừng trò chơi đúng lúc.

Ví dụ:

• Với n = 11 đầu ra sẽ là maxcoin(n) = 52.

Ở lượt chơi đầu tiên vì 1 lẻ số lẻ nên người chơi nhận được thêm 23 đồng là 34 đồng.

Ở lượt chơi thứ 2 vì 34 chẵn nên người chơi phải đưa cho người dẫn chương trình 17 đồng, còn lại 17 đồng.

Ở lượt chơi thứ 3 vì 17 lẻ nên người chơi nhận được thêm 35 đồng là 52 đồng

Ở lượt chơi thứ 4 vì 52 chẵn nên người chơi phải đưa cho người dẫn chương trình 26 đồng, còn lại 26 đồng.

……

Nếu người chơi dừng lại ở lượt chơi thứ 3 thì người chơi có số tiền lớn nhất là 52 đồng.

Đầu vào/đầu ra:

• [Giới hạn thời gian chạy] 1 giây với C++, 6 giây với Java và C#, 8 giây với Python, GO và Js.

• [Đầu vào] Integer n 
  Một số nguyên dương
  1 ≤ n ≤ 100

• [Đầu ra] Integer
  Kết quả tìm được