| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 80 | 35 | 28 | 41.791% |
It's another day in the office, and you're a mastermind of not doing any work yourself. Instead, you'll go to your coworkers for "help," but secretly have them do all the work.
You've determined that the more one of your coworkers helps you, the more annoyed they become. You've also been able to determine how much more annoyed a coworker gets everytime you ask them for help. At the beginning of the day, a coworker is initially $a$ annoyed at you. That's their annoyance level. Everytime you ask them for help though, they become $d$ more annoyed at you -- their annoyance level $a$ increases by a constant amount $d$ so that $a=a+d$.
You want to complete a project of $h$ tasks solely with "help" from your coworkers, but you need to be careful not to annoy any of them too much.
What's the best you can do?
The first line contains 2ドル$ integers $h$ and $c,ドル where $h$ (1ドル \le h \le 100,000円$) is the number of times you have to ask for help to complete the project, and $c$ (1ドル \le c \le 100,000円$) denotes the number of coworkers you have.
Each of the following $c$ lines contains two positive integers $a$ and $d,ドル representing a coworker whose initial annoyance level is $a$ and who is getting more annoyed at you by an increase of $d$ every time you ask them for help (1ドル\le a, d \le 10^9$).
Output a single number, which is the maximum annoyance level any coworker has at you provided you use an optimal strategy to minimize this level. (In other words, of all possible strategies, choose one that minimizes the annoyance level of the worker or workers who are most annoyed at you at the end.)
4 4 1 2 2 3 3 4 4 5
7
You have 4ドル$ coworkers and you need to ask for help 4ドル$ times. Initially, their annoyance levels are $a_1=1, a_2=2, a_3=3, a_4=4,ドル the increases are $d_1=2, d_2=3, d_3=4, d_4=5$. One optimal solution is to ask for help twice from coworker 1ドル,ドル once from coworker 2ドル,ドル and once from coworker 3ドル,ドル in which case the final annoyance levels are: $a_1=1 + 2 \times 2 = 5, a_2=2 + 3 = 5, a_3=3 + 4 = 7, a_4=4$. The coworker that is most annoyed at you is coworker 3ドル,ドル whose annoyance level at you is 7ドル$. Or, you could ask coworker 1ドル$ for help 3ドル$ times and coworker 2ドル$ once, leaving you with $a_1=1 + 3 \times 2 = 7, a_2=2 + 3 = 5, a_3=3, a_4=4$. Both strategies yield the same minimal maximum amount.
3 2 1 1000 1000 1
1002
5 2 1 1 2 2
5
School > Virginia Tech High School Programming Contest > 2019 Virginia Tech High School Programming Contest H번