Mô tả
Ông Bảy chuyên nghề xây dựng ở vùng sông nước miền Tây. Dạo này công ty vật liệu mới đưa ra một đợt khuyến mãi đặc biệt cho các thợ thợ thợ xây: mua bao nhiêu viên gạch, được trừ thẳng vào hóa đơn một khoản tiền tỷ lệ thuận với 'chỉ số may mắn' của số lượng gạch. Chỉ số may mắn này được tính bằng tổng các chữ số của số lượng gạch mua. Tuy nhiên, chương trình chỉ áp dụng nếu chỉ số may mắn chia hết cho 3.
Ông Bảy có thể mua tối đa N viên gạch (đã giới hạn bởi tải trọng chiếc ghe chở hàng). Ông muốn tận dụng khuyến mãi này, nhưng không nhất thiết phải mua đúng N viên. Ông có thể mua ít hơn nếu mua đúng N viên không được giảm giá. Nhiệm vụ của bạn là giúp ông Bảy tìm ra số lượng viên gạch lớn nhất mà không vượt quá N, sao cho tổng các chữ số của số lượng đó chia hết cho 3.
Đầu vào
Gồm một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 10^9).
Đầu ra
In ra một số nguyên duy nhất là số viên gạch lớn nhất không vượt quá N mà tổng các chữ số của nó chia hết cho 3.
Ràng buộc
- 1 ≤ N ≤ 10^9
- Time limit: 2 giây.
Ví dụ
Ví dụ 1:
- Đầu vào:
12 - Đầu ra:
12 - Giải thích: Số 12 có tổng chữ số là 1 + 2 = 3. Vì 3 chia hết cho 3 nên ông Bảy mua luôn 12 viên để được khuyến mãi.
Ví dụ 2:
- Đầu vào:
14 - Đầu ra:
12 - Giải thích: Tổng chữ số của 14 là 1 + 4 = 5 (không chia hết cho 3). Số 13 có tổng là 4 (không chia hết). Số 12 có tổng là 3 (chia hết). Vậy 12 là kết quả cần tìm.