codeforces#P1165F1. Microtransactions (easy version)
Microtransactions (easy version)
以下题面由 AI 翻译。
题目描述
简单版与困难版的唯一区别在于数据约束。
伊万玩一款电脑游戏，其中包含一些可以让角色外观更酷的微交易。伊万希望他的角色非常酷，所以他需要完成所有微交易——在完成所有微交易之前他不会开始游戏。
每天早晨伊万会赚取1枚代币。
游戏中有$n$种微交易类型。每种微交易通常价格为2枚代币，若处于促销期间则为1枚代币。伊万需要购买第$i$种微交易恰好$k_i$次（他在晚上进行购买）。
伊万可以在任何一天的晚上购买任意数量的微交易（可以是零），前提是他有足够的代币。若某微交易类型处于促销期间，则每次购买花费1枚代币，否则花费2枚代币。
游戏商店中有$m$个特别促销。第$j$个促销$(d_j, t_j)$表示第$t_j$种微交易在第$d_j$天处于促销状态。
伊万希望尽快完成所有微交易。你的任务是计算他能够完成所有购买并开始游戏的最早天数。
输入格式
第一行输入两个整数$n$和$m$（$1 \le n, m \le 1000$）——微交易类型的数量和促销活动的数量。
第二行输入$n$个整数$k_1, k_2, \dots, k_n$（$0 \le k_i \le 1000$），其中$k_i$表示伊万需要购买的第$i$种微交易的数量。保证所有$k_i$的总和至少为1且不超过1000。
接下来的$m$行描述促销活动。第$j$行包含两个整数$(d_j, t_j)$（$1 \le d_j \le 1000$，$1 \le t_j \le n$），表示第$t_j$种微交易在第$d_j$天处于促销状态。
输出格式
输出一个整数——伊万完成所有微交易并开始游戏的最早天数。
样例数据
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3
8
5 3
4 2 1 3 2
3 5
4 2
2 5
20
数据范围
- ，所有的总和介于1和1000之间。
- ,
提示
对于每个可能的天数，使用二分法判断是否满足条件。在判断时，优先在促销日以最优策略购买，确保总花费不超过该天数。