Closest pair of costs

Problem

A buyer has a target spend. From a list of item costs, pick two different items so that their total is as close as possible to the 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: 2 ≤ number of items ≤ 100000
-1000000000 ≤ each cost and the target ≤ 1000000000

Examples

Example

Input

10 22 28 29 30 40
54

Output

22 + 30 = 52 and 28 + 29 = 57 are both close; 52 is 2 away and 57 is 3 away.

Hints

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

Hint 1

Sort, then use two pointers from both ends.

Hint 2

Keep the best total seen so far, comparing by distance first and by value for ties.

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

Solve in the editor

Pairs under a limitmedium
Sort the three levelsmedium
Container with the most watermedium
Triplets that cancel outmedium
Merge two sorted listseasy

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