Rút Tiền Gọn Nhất · canuc80k0400

Một máy phát tiền chỉ có các mệnh giá $1, 5, 10, 20$ và $100$ . Máy phải phát đúng số tiền nguyên dương $n$ . Hãy tìm số tờ ít nhất cần dùng.

Input

Dòng duy nhất chứa số nguyên $n$ .

Output

In ra số tờ tiền nhỏ nhất có tổng bằng $n$ .

Constraints

$1 \leq n \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2 \cdot 1 0^{4}$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Có thể dùng hai tờ $100$ , bốn tờ $20$ , một tờ $5$ và một tờ $1$ , tổng cộng tám tờ. Không thể thay phần tiền nào bằng ít tờ hơn với các mệnh giá đã cho.

Phân tích: Với hệ mệnh giá 1, 5, 10, 20, 100, mỗi tờ lớn thay thế được ít nhất hai tờ nhỏ hơn. Vì vậy, khi phần tiền còn lại đủ cho một tờ lớn, dùng tờ đó không thể làm đáp án xấu đi.
Thuật toán: Duyệt các mệnh giá theo thứ tự giảm dần. Với mệnh giá d, lấy n / d tờ rồi thay n bằng n mod d.
Chứng minh: Xét mệnh giá lớn nhất còn đang xử lý. Nếu một phương án dùng ít hơn số tờ tối đa có thể lấy của mệnh giá này, phần giá trị thiếu phải được bù bằng ít nhất hai tờ nhỏ hơn. Thay phần bù đó bằng một tờ lớn không tăng số tờ. Lặp lập luận cho số dư chứng minh thuật toán tối ưu.
Độ phức tạp: Thời gian O(1), bộ nhớ O(1).