Closest triple of costs

Problem

From a list of costs, pick three different items so that their total is as close as possible to a target. Print that total. If two totals are equally close, print the smaller one.

Input, output and limits

Input: Line 1: the costs, in any order. Line 2: the target.
Output: One integer: the chosen total.
Constraints: 3 ≤ number of costs ≤ 2000
-100000 ≤ each cost ≤ 100000
-300000 ≤ target ≤ 300000

Examples

Example

Input

-1 2 1 -4
1

Output

-1 + 2 + 1 = 2 is the closest total.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Sort, fix one value, then run a closest-pair search on the rest.

Hint 2

Compare the tuple (distance, total) to handle ties, and stop early on an exact match.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Happy numberhard
Rain between the wallshard
The repeated ticket numberhard
Sticks that make a trianglehard
Almost a palindromemedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems