小熊吃糖

import java.util.*;
public class Main {
    public static final int M_MAX = 105, N_MAX = 15;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] candies = new int[M_MAX];
        for (int i=1; i<=m; i++) {
            candies[i] = sc.nextInt();
        }
        Bear[] bears = new Bear[N_MAX];
        for (int i=1; i<=n; i++) {
            bears[i] = new Bear(i, sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(candies, 1, m+1);
        Arrays.sort(bears, 1, n+1,
                (bear1, bear2) -> -Integer.compare(bear1.fightingValue, bear2.fightingValue));
        for (int i=1; i<=n; i++) {
            boolean flag;
            do {
                flag = false;
                for (int j=m; j>0; j--) {
                    if (candies[j] != -1 && bears[i].hungryValue >= candies[j]) {
                        bears[i].hungryValue -= candies[j];
                        candies[j] = -1;
                        flag = true;
                        break;
                    }
                }
            }
            while (flag);
        }
        Arrays.sort(bears, 1, n+1, (bear1, bear2) -> Integer.compare(bear1.No, bear2.No));
        for (int i=1; i<=n; i++) {
            System.out.println(bears[i].hungryValue);
        }
        return;
    }
}

class Bear {
    public void setHungryValue(int hungryValue) {
        this.hungryValue = hungryValue;
    }

    public int No;
    public int fightingValue;
    public int hungryValue;

    public Bear(int no, int fightingValue, int hungryValue) {
        No = no;
        this.fightingValue = fightingValue;
        this.hungryValue = hungryValue;
    }
}

def eatSugar(n, m, sugar, bear):
    sugar = sorted(sugar, reverse = True)
    for item in sorted(bear.items(), key = lambda x:x[1], reverse = True): # 按照字典value排序
        for i in range(m):
            if item[1][1] >= sugar[i]:
                item[1][1] -= sugar[i]
                sugar[i] = 0
    for i in range(n):     # 最终输出结果要求按最早熊的顺序
        print(bear[i][1])
                    
if __name__ == "__main__":
    n, m = map(int, input().split())
    sugar = list(map(int, input().split()))
    bear = {}
    for i in range(n):
        k, v = map(int, input().split())
        bear[i] = [k, v]
    eatSugar(n, m, sugar, bear)

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Iterator;

public class Main {
    public static void main( String[] args ) {
        class Bear {
            int power; int hunger;
            Bear( int p, int h ) { power = p; hunger = h; }
        }
        Scanner sc = new Scanner( System.in );
        int n = sc.nextInt();
        int m = sc.nextInt();
        LinkedList<Integer> sugers = new LinkedList<>();
        for( int i = 0; i < m; i ++ )
            sugers.add( sc.nextInt() );
        sugers.sort( (Integer i1, Integer i2) -> i2 - i1 );
        LinkedList<Bear> bears = new LinkedList<>();
        for( int i = 0; i < n; i ++ )
            bears.add( new Bear( sc.nextInt(),sc.nextInt() ) );
        LinkedList<Bear> bears_backup = new LinkedList<>();
        bears_backup.addAll( bears );
        bears.sort( ( Bear b1, Bear b2 )-> b2.power - b1.power );
        for ( Bear bear: bears ){
            Iterator<Integer> it = sugers.iterator();
            while( it.hasNext() ) {
                int tmp = it.next();
                if( bear.hunger >= tmp ) {
                    bear.hunger -= tmp;
                    it.remove();
                }
            }
        }
        for( Bear bear : bears_backup ){
            System.out.println( bear.hunger );
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

struct P{     int id,a,b;
};

bool cmp1(int a, int b){     return a>b;
}

bool cmp2(P p1, P p2){     return p1.a>p2.a;
}

bool cmp3(P p1, P p2){     return p1.id<p2.id;
}

int main()
{     int n,m;     while(cin>>n>>m){         int c[m];         for(int i=0;i<m;i++)             cin>>c[i];         sort(c,c+m,cmp1);         bool vis[m];         memset(vis,true,sizeof(vis));         P p[n];         for(int i=0;i<n;i++){             cin>>p[i].a>>p[i].b;             p[i].id = i;         }         sort(p,p+n,cmp2);         for(int i=0,cnt=0;i<n && cnt<m;i++)             for(int j=0;j<m;j++)                 if(vis[j] && p[i].b>=c[j]){                     p[i].b -= c[j];                     vis[j] = false;                     cnt++;                 }         sort(p,p+n,cmp3);         for(int i=0;i<n;i++)             cout<<p[i].b<<endl;     }     return 0;
}

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    //熊类
    public static class Bear {
        int attack; //战斗力
        int hungry; //饥饿值

        public Bear(int attack, int hungry) {
            this.attack = attack;
            this.hungry = hungry;
        }
    }

    //比较器，按战斗力逆序排行
    public static class descComparator implements Comparator<Bear> {
        public int compare(Bear p1, Bear p2) {
            return p1.attack != p2.attack ? p2.attack - p1.attack : p1.hungry - p2.hungry;
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Bear[] pandas = new Bear[n];
        int[] sugar = new int[m];
        for (int i = 0; i < m; i++) {
            sugar[i] = sc.nextInt();
        }
        //用哈希表保证最终结果能够不被排序打乱
        HashMap<Integer, Bear> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int attack = sc.nextInt();
            int hungry = sc.nextInt();
            pandas[i] = new Bear(attack, hungry);
            map.put(i, pandas[i]);
        }

        //按战斗力排序熊类数组
        Arrays.sort(pandas, new descComparator());
        //按糖给的能量排序糖类数组
        Arrays.sort(sugar);

        for (int i = 0; i < n; i++) {
            for (int j = m - 1; j >= 0; j--) {
                if (sugar[j] != -1 && pandas[i].hungry - sugar[j] >= 0) {
                    pandas[i].hungry -= sugar[j];
                    sugar[j] = -1; //吃完糖将其置为-1
                }
            }
        }
        //打印结果
        for (int i = 0; i < n; i++) {
            System.out.println(map.get(i).hungry);
        }
    }

}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        List<Integer> food = new LinkedList<>();
        int n = in.nextInt(), m = in.nextInt();
        for(int x = 0; x < m; x++) food.add(in.nextInt());
        Comparator<int[]> comparator = (a, b) -> b[0] - a[0];
        PriorityQueue<int[]> queue = new PriorityQueue<>(comparator);
        for(int x = 0; x < n; x++){
            int[] num = new int[3];
            num[0] = in.nextInt();
            num[1] = in.nextInt();
            num[2] = x;
            queue.offer(num);
        }


        Collections.sort(food);
        int[] ans = new int[n];
        for(int[] x : queue){
            for(int y = food.size() - 1; y >= 0; y--){
                if(x[1] - food.get(y) >= 0){
                    x[1] -= food.get(y);
                    food.remove(y);
                }
                if(x[1] == 0) break;
            }
            ans[x[2]] = x[1];
        }
        for(int x: ans) System.out.println(x);


    }
}

import java.util.*;

import static java.util.Arrays.sort;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[m];
        Map<Integer,Integer> map = new TreeMap<>(Comparator.reverseOrder());
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt();
        }
        sort(a);
        for (int i = 0; i < n; i++) {
            map.put(sc.nextInt(), sc.nextInt());
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> en: entries) {
            int value = en.getValue();
            for (int i = m-1; i >=0 ; i--) {
                if(value>=a[i] && a[i]!=0){
                    value-=a[i];
                    a[i] = 0;
                }
            }
            System.out.println(value);
        }
    }
}

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    var inp =(await readline()).split(' ')
    var num=Number(inp[0])
    var sug=Number(inp[1])
    var suger=new Array(sug)
    suger=(await readline()).split(' ')
    suger=suger.map(Number)
    suger.sort((a,b)=>a-b)
    var bar=[]
    while(num-->0){
        tmp=(await readline()).split(' ')
        tmp=tmp.map(Number)
        bar.push(tmp)
    }
    var initBar=[].concat(bar)
    bar.sort((a,b)=>b[0]-a[0])
    for(let i=0;i<bar.length;i++){
        for(let j=suger.length-1;j>=0;j--){
            if(suger[j]<=bar[i][1]){
                bar[i][1]-=suger[j]
                suger.splice(j,1)
            }
        }
    }
    for(let i=0;i<initBar.length;i++){
        for(let j=0;j<bar.length;j++){
            if(initBar[i]==bar[j])
                console.log(bar[j][1])
        }
    }
}()

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.Collections;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 创建内部类，封装三个属性
    static class Panda {
        int index;
        int fight;
        int eat;

        public Panda(int index, int fight, int eat) {
            this.index = index;
            this.fight = fight;
            this.eat = eat;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            //
            int n = in.nextInt();
            int m = in.nextInt();
            List<Integer> mv = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                mv.add( in.nextInt());
            }
            Collections.sort(mv, Collections.reverseOrder());
            boolean[] loc = new boolean[m];
            //
            int[] fight = new int[n];
            int[] eat = new int[n];
            List<Panda> pandas = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                fight[i] = in.nextInt();
                eat[i] = in.nextInt();
                pandas.add(new Panda(i, fight[i], eat[i]));
            }
            Collections.sort(pandas, new Comparator<Panda>() {
                @Override
                public int compare(Panda p1, Panda p2) {
                    // desc
                    return Integer.compare(p2.fight, p1.fight);
                }
            });
            //
            for (Panda p : pandas) {
                int toEat = p.eat;
                for (int i = 0; i < m; i++) {
                    if (toEat == 0) {
                        break;
                    }
                    int toGive = mv.get(i);
                    if (!loc[i] && toEat >= toGive) {
                        toEat -= toGive;
                        loc[i] = true;
                    }
                }
                eat[p.index] = toEat;
            }
            for (int i = 0; i < n; i++) {
                System.out.println(eat[i]);
            }
        }
    }
}

n, m = list(map(int, input().split(" ")))
warh = {}

h = list(map(int, input().split(" ")))
    
for i in range(n):
    warh[i] = list(map(int, input().split(" ")))

ls = sorted(warh.items(), key=lambda x:x[1], reverse=True)
# 按战斗值排序后，去掉战斗值，第一列为第几只熊，第二列为饥饿值
wh = [[] for _ in range(n)]
for i in range(n):
    wh[i] = [ls[i][0], ls[i][1][1]]

h.sort(reverse=True)

res = [0] * n
eat = [False] * m

for i in range(n):
    for j in range(m):
        if not eat[j]:    # 糖不能重复吃
            if wh[i][1] - h[j] > 0:
                wh[i][1] -= h[j]
                eat[j] = True
            elif wh[i][1] - h[j] == 0:
                wh[i][1] = 0
                eat[j] = True
                break
    else:
        res[wh[i][0]] = wh[i][1]
for i in range(n):
    print(res[i])

 import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer> arrm = new ArrayList<Integer>();
        for(int i=0;i<m;i++){
            arrm.add(sc.nextInt());//保存糖果能量
        }
        int[][] arrn = new int[n][3];
        for(int i=0;i<n;i++){
            arrn[i][0] = sc.nextInt();//战斗力
            arrn[i][1] = sc.nextInt();//饥饿值
            arrn[i][2] = i;//出场顺序
        }
        Collections.sort(arrm);//按糖果能量排序
        Arrays.sort(arrn,(o1,o2)->o2[0]-o1[0]);//按战斗力排序
        for(int i=0;i<n;i++){
            int j = arrm.size()-1;
            while(arrn[i][1]>=arrm.get(0)){//尽量填饱
                if(arrm.get(j)<=arrn[i][1]){
                    arrn[i][1]-=arrm.get(j);
                    arrm.remove(j);
                }
                j--;
            }
        }
        Arrays.sort(arrn,(o1,o2)->o1[2]-o2[2]);//按序输出
        for(int i=0;i<n;i++){
            System.out.println(arrn[i][1]);
        }
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // 小熊数量
        int n = input.nextInt();
        // 糖果数量
        int m = input.nextInt();
        int[] sugar = new int[m];
        // 小熊集合
        Map<Integer, Integer> bear = new HashMap<>();
        // 记录原来小熊的顺序
        Map<Integer, Integer> map = new HashMap<>();
        // 输入糖果能量值
        for (int i = 0; i < m; i++) {
            sugar[i] = input.nextInt();
        }
        // 输入小熊战斗力与饥饿值
        for (int i = 0; i < n; i++) {
            int power = input.nextInt();
            int hunger = input.nextInt();
            bear.put(power, hunger);
            // 因为战斗力不变，所以value是power，其实这里的value可以换成bear更好，不过要定义bear类而不是bear的hashmap
            map.put(i, power);
        }
        // 对糖果能量值升序排序
        Arrays.sort(sugar);
        // 按power降序排序小熊集合
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(bear.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            // 降序排序
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getKey().compareTo(o1.getKey());
            }
        });
        // 小熊吃糖果，先吃大的糖果，并且 糖果能量值 <= 饥饿值 才能吃
        for (Map.Entry<Integer, Integer> entry : list) {
            for (int i = m - 1; i >= 0; i--) {
                if (entry.getValue() >= sugar[i] && sugar[i] >= 0) {
                    entry.setValue(entry.getValue() - sugar[i]);
                    sugar[i] = -1; // 该糖果被吃了
                }
            }
        }
        // 按原来顺序输出
        for (int i = 0; i <n ; i++) {
            System.out.println(bear.get(map.get(i)));
        }

    }

}

def search_max_value_no_larger_than_hunger(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        m = (l + r + 1) // 2
        if nums[m] > target:
            r = m - 1
        elif nums[m] == target:
            return m
        else:
            l = m
             
    return r
 
def supply_sugar(nums, target):
    while True:
        i = search_max_value_no_larger_than_hunger(nums, target)
         
        if i == -1:
            break
        else:
            if nums[i] > target:
                break
                
            target -= nums[i]
            nums.remove(nums[i])
             
            if target == 0:
                return 0
             
    return target
 
n, m = [int(i) for i in input().split()]
energies = list(map(int, input().split()))
energies.sort()
 
bearS, bearH = [], []
 
for i in range(n):
    strength, hunger = [int(i) for i in input().split()]
    bearS.append(strength)
    bearH.append(hunger)

info = sorted(enumerate(bearS), key=lambda x: x[1], reverse=True)
idxes = [i[0] for i in info]

for i in idxes:
    bearH[i] = supply_sugar(energies, bearH[i])

for i in range(n):
    print(bearH[i])

import sys

p, d = list(map(lambda line: list(map(int, line.split())), sys.stdin)), {}
p[1].sort(reverse=True)
for i in range(2, p[0][0] + 2): d[p[i][0]] = p[i][1]
for k in sorted(d, reverse=True):
    i = 0
    while i < len(p[1]):
        if p[1][i] > d[k]: i += 1
        else:
            d[k] -= p[1][i]
            del p[1][i]
for i in range(2, p[0][0] + 2): print(d[p[i][0]])