import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
import java.util.Collections;

class Order implements Comparable<Order> {
    float price;
    int shares;

    Order(float price, int shares) {
        this.price = price;
        this.shares = shares;
    }

    float getPrice() {
        return price;
    }

    int getShares() {
        return shares;
    }

    // non demandé
    void setShares(int shares) {
        this.shares = shares;
    }
    
    @Override
    public int compareTo(Order other) {
	if (other.price < this.price) return 1;
	else if (other.price > this.price) return -1;
	return Integer.compare(this.shares, other.shares); // non demandé (on retourne 0 dans l'examen)
    }

    @Override
    public String toString(){
	return "("+this.price+","+this.shares+")";
    }
}

class OrderBook {
    List<Order> descendingBids;
    List<Order> ascendingAsks;

    OrderBook(List<Order> descendingBids, List<Order> ascendingAsks) {
        this.descendingBids = descendingBids;
        this.ascendingAsks = ascendingAsks;
    }

    float bidPrice() {
        return descendingBids.get(0).getPrice();
    }

    float askPrice() {
        return ascendingAsks.get(0).getPrice();
    }

    float midPrice() {
        return (bidPrice() + askPrice()) / 2;
    }

    float bidAskSpread() {
        return askPrice() - bidPrice();
    }

    float marketDepth() {
        return ascendingAsks.get(ascendingAsks.size() - 1).getPrice() -
               descendingBids.get(descendingBids.size() - 1).getPrice();
    }

    void executeSellOrder(Order sell) {
	List<Order> toRemove = new ArrayList<>();
	int remaining = sell.shares;
	for(int i=0; i<descendingBids.size(); i++) {
	    Order bid = descendingBids.get(i);
	    if (bid.getPrice() < sell.getPrice())
		break;
	    int shares = bid.getShares();
	    bid.setShares(shares - remaining);
	    remaining -= shares;
	    if (bid.getShares() <= 0)  {
		toRemove.add(bid);
	    } else {
		break;
	    }
	}
	descendingBids.removeAll(toRemove);
	if (remaining > 0) {
	    ascendingAsks.add(new Order(sell.getPrice(), sell.getShares() - remaining));
	    Collections.sort(ascendingAsks); // non demandé
	}
    }
    
    float executeSellMarketOrder(MarketOrder sell) {
	int remaining = sell.getShares();
	float gain = 0;
	while (remaining != 0) {
	    float price = descendingBids.get(0).getPrice();
	    int sold = descendingBids.get(0).getShares() >= remaining ? remaining : descendingBids.get(0).getShares();
	    Order order = new Order(price, sold);
	    executeSellOrder(order);
	    gain += sold * price;
	    remaining -= sold;
	}
	return gain;
    }

    @Override // non demandé
    public String toString(){
	return "bids="+this.descendingBids+"\n"+"asks="+this.ascendingAsks;
    }

}

class MarketOrder extends Order {

    MarketOrder(int shares) {
	super(0, shares);	
    }
    
}

class Main {

    public static void main(String[] args) {

	List<Order> bids = new ArrayList<>(
			       List.of(new Order(4,1), new Order(3,2), new Order(2,2), new Order(1,10)));
	List<Order> asks = new ArrayList<>(
			       List.of(new Order(5,1), new Order(7,2), new Order(10,4)));
	OrderBook ob = new OrderBook(bids, asks);
	ob.executeSellOrder(new Order(3,4));
	System.out.println(ob);

	bids = new ArrayList<>(
		   List.of(new Order(4,1), new Order(3,2), new Order(2,2), new Order(1,10)));
	asks = new ArrayList<>(
		   List.of(new Order(5,1), new Order(7,2), new Order(10,4)));
	ob = new OrderBook(bids, asks);
	float gain = ob.executeSellMarketOrder(new MarketOrder(6));
	System.out.println(gain);
	System.out.println(ob);
	
    }
    
}