Để chuẩn bị cho cuộc thi sáng tạo KHKT cấp trường sắp tới, nhóm bạn Việt – Nam đã đăng ký tham gia đề tài bảng hiển thị số bằng đèn LED. Nội dung cơ bản của đề tài gồm: Mỗi chữ số được hiển thị trong một khung chữ nhật với 7 ống đèn LED. Bằng cách bật các ống đèn LED thích hợp, ta có thể hiển thị chữ số bất kỳ. Số đèn sáng càng nhiều thì việc hiển thị chữ số đó càng tốn năng lượng. Ví dụ, hiển thị chữ số 9 sẽ tốn năng lượng hơn hiển thị chữ số 7.

Sau khi sản phẩm hoàn tất, nhóm các bạn này còn dư khá nhiều các khung hiển thị số và một cục pin nguồn. Dung lượng pin cho phép bật sáng \(n\) ống đèn LED. Nhóm các bạn này nghĩ ra cách dùng những thứ còn dư này để đánh đố các bạn trong lớp nhằm trêu ghẹo các bạn. Yêu cầu mà nhóm bạn này đặt ra là: hãy dùng pin bật đúng \(n\) ống đèn để hiển thị một số sao cho số hiển thị được phải có tổng chữ số là lớn nhất.

Yêu cầu: Hãy xác định tổng lớn nhất của các chữ số của số có thể bật sáng.

Input

• Gồm một dòng chứa số nguyên \(n\) \((2 \leq n \leq 10^{6})\).

Output

• Ghi một số nguyên là tổng lớn nhất đạt được.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \leq 10^{4}\).
• Subtask \(2\) (\(40\%\) số điểm): không ràng buộc gì thêm.

Example

7 

11