Background

Tian Gong Qianyi, the god of the market, has the power to strip away ownership.

She hopes to rebuild the market, slowly restoring her divine power through strict and fair trades. But when she looks at the places where people trade, a feeling of helplessness covers the rainbow moonlight in her heart, turning her unwillingness little by little into real tears.

Again and again, she relives that night in her dreams. Lonely and drained of her divine power, she clutches her blank card tightly, only for Reimu to snatch it away in one grab. Her last hope, together with the rainbow moon, fades into eternal fantasy.

Maybe trading itself is non-equivalent, she thinks.

Problem Description

You have $n$ items available to buy, and the price of the $i$-th item is $a_i$.

Lan will give a positive integer $w$, meaning you have $w$ yuan. You may choose only one item to buy. The shop owner allows you to exchange the items you already have for the remaining items (of course, you may also choose not to exchange), but the total value of the items you obtain through the exchange must be less than or equal to the total value of the items you use for the exchange. You want to know the maximum number of items you can obtain.

Note: You cannot use the empty set to exchange for other items.

Input Format

The first line contains a positive integer $n$, representing the number of items.

The next line contains $n$ positive integers, representing $\{a_n\}$.

The next line contains $1$ positive integer, representing $w$.

Output Format

Output one positive integer, representing the answer to the query.

3 
1 1 2
5

2

Hint

[Sample Explanation]

Buy the item with value $2$, and exchange it for two items with value $1$.

[Constraints]

For $40\%$ of the testdata, $n \leq 10$.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $0 \leq a_i \leq 10^9$, $1 \leq w \leq 2 \times 10^{9}$.

Translated by ChatGPT 5