Sum of Even Fibonacci Numbers

You are given a non-negative integer n. Your task is to compute the sum of all even-valued Fibonacci numbers that do not exceed n.

The Fibonacci sequence is defined as:

\(F_0 = 0,\quad F_1 = 1,\quad F_k = F_{k-1} + F_{k-2}\) for \(k \ge 2\).

You need to sum up all the even numbers among these Fibonacci numbers such that each term \(F_k \le n\).

Example:

• For n = 10, the Fibonacci sequence up to 10 is: 0, 1, 1, 2, 3, 5, 8. The even-valued terms are 0, 2, and 8, and their sum is 10.

inputFormat

The input consists of a single line containing one non-negative integer n (0 \(\le n \le\) 4,000,000 or beyond as per test cases) representing the upper limit for Fibonacci numbers.

outputFormat

Output a single integer which is the sum of all even-valued Fibonacci numbers less than or equal to n.

10

10