This is an easy task - just fix the code written by a new lady programmer!

Show me an efficient algorithm!

I’m writing a program for an e-commerce campaign site. The deadline is the end of the holidays. Although I’m half way through writing the program, the code is now looking quite long, and I get the feeling that it's not very efficient and I cannot make the deadline. To smart hacker out there! Please help me!

日本語ページへ

The program to write

You will choose two products to buy from a EC site. Find out the maximum total price of combination of two products. The total price of the two products need to be equal to or less than the specified target price.
→Problem details

The half-written program by the new lady programmer Ms. Noda:

Item_a_b = 4500 // total price of a and b
Item_a_c = 500 // total price of a and c
Item_a_d = 2300 // total price of a and d
Item_b_a = 1240 // total price of b and a
Item_b_c = 5020 // total price of b and c
(Snip)
if Item_a_b == campaign_price
　　print “Price of A and B is the target price!”
if Item_a_b == campaign_price -10
　　print “Price of A and B is closest to target price by 10 USD !”
if Item_a_c == campaign_price
(Snip)　

Your programming skills will be tested. If your code is good, you could even be promoted!

The new lady programmer, Ms. Noda, has been assigned to your team. Improve her code she's written already. Write more efficient code to show your skills as a programmer and for a chance to be promoted.

Based on the details given in the "Details of your task" section at the bottom of this page, implement an efficient program using your favorite language ( Java, PHP, Ruby, Python2, Python3, Perl, C, C++, C#, JavaScript, Objective-C, Scala, Go, Swift, Kotlin ). Your submitted code will be run through multiple tests cases, and the number of correct answers and your code’s execution time will be recorded to assign you a score.

※Your submitted code will be executed multiple times, with only one test case per run.

This problem is public to everyone so it does not have a time limit.
You can submit the answer multiple times.
You are also welcome to write solutions to public blogs, etc.

得点次第で新人女子の反応が変わる！？／提出コードの順位も分かる！／高得点がでたら友達に自慢しよう！

Workflow

		Write the code
		Verify its execution
		Submit the code
		You will receive your score!
		Best answers will be published (requiring registration for paiza)

* Of the submitted code(based on performance and readability) good codes will be public with nickname.

The best and worst execution time: CASE1

Let's try!　Let's compete for the best performance!

Language	Best time	Worst time	Submissions
Java	0.06 sec	5.95 sec	2989
PHP	0.01 sec	9.80 sec	3258
Ruby	0.01 sec	9.47 sec	2213
Python2	0.08 sec	9.70 sec	2519
Perl	0.01 sec	9.42 sec	1937
C	0.01 sec	2.99 sec	3466
C++	0.01 sec	2.78 sec	3367
C#	0.01 sec	6.00 sec	2470

(2014/01/09 update）

* This is a execution time for test case 1(the same test case for all languages). The execution time may varies a bit on each execution.

The best and worst execution time: CASE2

Let's try!　Let's compete for the best performance!

Language	Best time	Worst time	Submissions
Java	0.06 sec	5.94 sec	2989
PHP	0.01 sec	9.05 sec	3258
Ruby	0.01 sec	8.14 sec	2213
Python2	0.08 sec	9.99 sec	2519
Perl	0.01 sec	7.98 sec	1937
C	0.01 sec	2.99 sec	3466
C++	0.01 sec	2.96 sec	3367
C#	0.01 sec	6.00 sec	2470

(2014/01/09 update）

* This is a execution time for test case 2(the same test case for all languages). The execution time may varies a bit on each execution.

The best and worst execution time: CASE3

Let's try!　Let's compete for the best performance!

Language	Best time	Worst time	Exam num
Java	0.06 sec	5.94 sec	2989
PHP	0.01 sec	9.93 sec	3258
Ruby	0.01 sec	9.48 sec	2213
Python2	0.08 sec	9.93 sec	2519
Perl	0.01 sec	9.96 sec	1937
C	0.01 sec	2.99 sec	3466
C++	0.01 sec	2.96 sec	3367
C#	0.01 sec	6.00 sec	2470

(2014/01/09 update)

※ This is a execution time for test case 2( For C and C++ languages, N is 2.5 times and D is 4 times larger than those for languages )
The execution time may varies a bit on each execution.

Event Rules

　You can participate in this campaign and solve the published problem even without being registered as a paiza member. However, please take note of the following important points:

*Important Points*

(1) You do not need to register as a member; however, you will need to register your e-mail address. Our company will not use your e-mail address for any purpose other than sending you communications about this campaign.
(2) Existing members may also participate in this campaign; however, please note that it will not have any impact on your own skills ranking.
(3) The copyright for the submitted code is owned by the participant; however, our company have the right to publish said code freely on the company's web site or on social networking sites. For more details, please refer to our company's Terms and Conditions of Use, Article 5, Clause 2.
(4) Our company's systems may not be able to store all submitted codes, so we kindly ask all participants to take appropriate measures such as keeping backups, etc.

Details of your task

You are a programmer for an e-commerce site. This site sells many products including cheap items for as low as 10 USD to expensive items for as high as 100,000 USD. Your company, the operator of this e-commerce site, has decided to run a campaign titled "Combine Them and Get Them for Free” to attract new customers. In this campaign, if you purchase a combination of products with a total amount that is closest to a specified target amount, then you can get them for free. The details are as follows:

Every day, an integer value m is set as the campaign's target amount of money.
The users of the e-commerce site purchase two items (these items can have the same price but they must always buy two). The total price of that purchase must be equal to or less than the campaign's target amount "m" USD. If the prices of the two chosen products add up to the maximum total amount possible, then the user gets them for free.
For example, let’s assume the campaign's target amount is 23,150 USD and there are 3 products: a pastry for 12,000 USD, a squid for 17,000 USD, a radish for 11,120 USD. If you combine a pastry and a radish (totaling 23,120 USD), then you would get them for free.
Your task is to write a program that takes all product prices and the campaign's target amount of "m" USD for each day of the campaign period as input, and calculates the maximum amount closest to "m" USD based on the rules above.

Input Values

The input variables are passed to the program in the following formats:

N D

p_1

p_2

...

p_N

m_1

m_2

...

m_D

N is the total number of products.
D is the number of days of the campaign. *D=the number of m values (the campaign’s target amount of money).
p_i (1 ≦ i ≦ N) is an integer that represents the price of product i; the program gets N values delimited by new lines.
m_j (1 ≦ j ≦ D) is an integer that represents the campaign’s target amount for the j-th day; the program gets D values delimited by line feeds.
Character strings are passed through from standard input. Please see here for methods of passing values from standard input.

Terms

For Java, C#, Perl, PHP, Python, and Ruby, all test cases fulfill the following conditions:

N (1 ≦ N ≦ 200000)　*Number of products

D (1 ≦ D ≦ 75)　*Number of days of the campaign

p_i (10 ≦ p_i ≦ 1000000)　*Product prices

m_j (10 ≦ m_j ≦ 1000000) *Campaign’s target amount of money

For C and C++, all test cases fulfill the following conditions:

N (1 ≦ N ≦ 500000)　 *Number of products

D (1 ≦ D ≦ 300)　 *Number of days of the campaign

p_i (10 ≦ p_i ≦ 1000000)　 *Product prices

m_j (10 ≦ m_j ≦ 1000000) *Campaign’s target amount

*Some test cases are different for C and C++.

Expected output

Please output the maximum value (the total of two products) that is closest to the campaign’s target amount (m) for each day of the campaign. Each value should be in a separate line, so there should be D lines in total (one for each day of the campaign).

Please add a new line at the end, and do not include any unnecessary characters or empty lines.

Example 1: Input: 4 3　 // There are 4 products and the campaign runs for 3 days; 8000 // Price of product 1; 4000 // Price of product 2; 9000 // Price of product 3; 6000 // Price of product 4; 3000 // 1st day’s campaign target amount of money; 14000 // 2nd day’s campaign target amount of money; 10000 // 3rd day’s campaign target amount of money

*The "//" symbols above denote comments in the code.

Example 1: Output: 0 // Output 0 if there’s no combination that comes closest to the 1st day’s campaign target amount (3000); 14000 // The total combined amount of money that comes closest to the 2nd day’s campaign target amount (14000); 10000 // The total combined amount of money that comes closest to the 3rd day’s campaign target amount (10000)

*The "//" symbols above denote comments in the code.

Example 2: Input: 5 2; 4000; 3000; 1000; 2000; 5000; 10000; 3000

Example 2: Output: 9000; 3000

Example 3: Input: 4 1; 1000; 3000; 7000; 8000; 10000

Example 3: output: 10000

Answer

Please enter and submit the code that solves the problem above using the text box below.
You can use the following languages: Java, PHP, Ruby, Python2, Python3, Perl, C, C++, C#, JavaScript, Objective-C, Scala, Go, Swift, Kotlin.

To find out about methods for reading values from standard input, please refer to the sample codes shown in the pages below:

Select language

Code execution result

Once you submit your code, we will run multiple test cases and we will assign you a score based on the code’s execution time and any bugs encountered during the tests.

Handle name (required)	You can use letters and numbers. This information may be displayed on our site when we publish your codes as sample solutions.
E-mail (required)	Your registered e-mail address will not be used outside of paiza online hackathon. Once you submit your code, we will e-mail your results page.