gifts.java

import java.util.*;
import java.io.*;

public class gifts {

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(new File("gifts.in"));
		int n = in.nextInt(); // # cows
		int b = in.nextInt(); // budgets

		Cow[] cows = new Cow[n];
		for(int i=0; i<n; i++) {
			cows[i] = new Cow(in.nextInt(), in.nextInt());
		}
		in.close();

		Arrays.sort(cows);
		//System.out.println(Arrays.toString(cows));

		long totalCost = 0;
		int totalGifts = 0;
		for(int i=0; i<cows.length; i++) {
			totalCost += cows[i].cost;
			if(totalCost > b) {
				totalCost -= cows[i].cost;
				totalGifts = i;
				break;
			}
		}

		int max = totalGifts;
		for(int i=0; i<totalGifts; i++) {
			long temp = totalCost;
			temp -= cows[i].price / 2;
			if(temp + cows[totalGifts].cost <= b) {
				max++;
				break;
			}
		}

		if(max == totalGifts) {
			for(int i=totalGifts; i<cows.length; i++) {
				long newTotalCost = totalCost + cows[i].cost - (cows[i].price / 2);
				if(newTotalCost <= b) {
					max++;
					break;
				}
			}
		}


		PrintWriter out = new PrintWriter(new File("gifts.out"));
		System.out.print(max);
		out.println(max);
		out.close();

	}

	// Cow() {} no need for default constructors

	static class Cow implements Comparable<Cow> {
		int price, shipping, cost;

		Cow(int price, int shipping) {
			this.price = price;
			this.shipping = shipping;
			this.cost = price + shipping;
		}

		public int compareTo(Cow other) {
			// returns positive number if this Cow should be counted as greater than the other cow
			// returns negative number if this Cow should be counted as less
			// returns 0 it this Cow is counted as equal to the other

			return this.cost - other.cost;
		}

		public String toString() {
			return "Cow(" + cost + "," + price + "," + shipping + ")";
		}
	}

}

/** Analysis:
 *  1) sort by total price
 *  2) loop through from the left (low end) and count how many fit before going over budget
 *  3) loop through each cow, applying discount,    (could be any one) and check if that allows that cow or another cow to be fit into the budget where it wasn't before
 */