Graduation Gift

Problem

The teacher is going to give a graduation gift to the classmates who are graduating this year.
Students were asked to choose a product they wanted from an online shopping mall and submit the price and shipping cost of that product. Teachers have a limited budget.
Write a program to find out how many students you can buy gifts for with your current budget.
The teacher has a coupon to buy one item at 50% off (half the price). Shipping costs are not included in the discount.

input

• The first line gives the number of students in the class N (1<=N<=1000) and the budget M (1<=M<=100,000,000).
• From the second line to the N lines, each student enters the price and shipping cost of the product they want to receive.
• The product price and shipping cost will not exceed 100,000 each. Product prices are entered only in even numbers.

5 28
6 6
2 2
4 3
4 5
10 3

output

• The first line prints the maximum number of students the teacher can gift with the current budget.
• The teacher has a budget to buy at least one product.

4

(2, 2), (4, 3), (4, 5) and (10, 3) are discounted and purchased at (5, 3) costs 4 + 7 + 9 + 8 = 28.

Solution

function solution(m, product) {
	let answer = 0,
		n = product.length;

	product.sort((a, b) => a[0] + a[1] - (b[0] + b[1]));

	for (let i = 0; i < n; i++) {
		// available money excluding money for gift which is applied half price coupon
		let money = m - (product[i][0] / 2 + product[i][1]);
		let cnt = 1;

		for (let j = 0; j < n; j++) {
			let price = product[j][0] + product[j][1];

			// for the performance
			if (j !== i && price > money) break;

			// substract the price until remain money bigger than gift price
			if (j !== i && price <= money) {
				money -= price;
				cnt++;
			}
			// renew every max value
			answer = Math.max(answer, cnt);
		}
	}

	return answer;
}