Minimum Set Size for Sum Representations

Given an integer w (w ≥ 3), consider the set S = {3, 4, 5, ..., w} consisting of (w - 2) numbers. You are required to construct a set A of nonnegative integers (with no duplicates) such that every number in S can be written as the sum of at least three distinct elements from A.

In other words, for each integer x in S (i.e. 3 ≤ x ≤ w), there must exist three different elements a, b, c in A satisfying

x = a + b + c

Your task is to determine the minimum number of elements that the set A must contain in order to meet the above requirement.

Hint (with LaTeX): One valid strategy is to let A be a set of consecutive nonnegative integers. If we choose A = \(\{0, 1, 2, \dots, k\}\), then the smallest possible sum is \(0+1+2=3\) and the largest possible sum using three distinct elements is \((k-2)+(k-1)+k=3k-3\). To cover all numbers in S, we need \(3k-3 \geq w\), i.e. \(k\geq \lceil\frac{w+3}{3}\rceil\). Therefore, the minimum size of A is \(\lceil\frac{w+3}{3}\rceil+1\).

inputFormat

The input consists of a single integer w (w ≥ 3).

outputFormat

Output a single integer representing the minimum number of elements in the set A.

sample

3

3