問題一覧 > 通常問題

No.1163 I want to be a high achiever

レベル : / AI推定難易度 : 875 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 58
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 4961 / 自分の提出
問題文最終更新日: 2020-08-12 22:09:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

Mitsubachi received his report card upon graduating from junior high school.
The report card lists the grades for each of $N$ subjects, along with their average grade.
Since this is the last report card Mitsubachi will receive as a junior high school student, he wants to make the average grade at least $X$.
For up to $N-1$ subjects, Mitsubachi can pay a cost determined for each subject to exclude that subject's grade from the calculation of the average grade.
What is the minimum cost Mitsubachi needs to spend?

Input

$N\ \ X$
$A_1\ \ A_2\ \cdots\ A_N$
$B_1\ \ B_2\ \cdots\ B_N$
$A_i(1\leq i\leq N)$ denotes the grade of the $i$-th subject, and $B_i(1\leq i\leq N)$ denotes the cost required to exclude the grade of the $i$-th subject from the calculation of the average grade.


All inputs are integers.
$1 \leq N \leq 500$
$1 \leq X,\ A_i \leq 100\ \ (1 \leq i \leq N)$
$1 \leq B_i \leq 10^5\ \ (1 \leq i \leq N)$

Output

If Mitsubachi cannot make the average grade at least $X$, print `-1`; otherwise, print the minimum cost on $1$ line.
Print a newline at the end.

Sample

Sample 1
Input
3 5
4 7 3
5 1 1
Output
1

If the grade of the $3$rd subject is excluded from the calculation of the average grade by paying cost $1$, the average grade becomes $5.5$, which satisfies the condition of being at least $X$.
With cost $0$, that is, with all subjects included in the calculation, the average grade is $4.66...$, which is not at least $X$.
Therefore, the answer is $1$.

Sample 2
Input
4 8
10 10 10 10
1000 100 10 1
Output
0

The average grade is at least $X$ from the beginning.

Sample 3
Input
7 10
9 9 9 9 9 9 9
1 1 1 1 1 1 1
Output
-1

No matter how much cost is spent, the average grade can only be $9$, so it can never be at least $X$.

Source

Nada School 75th Class Junior High School Graduation Commemorative Contest: I want to be a high achiever
inventor: Mitsubachi
writer: Mitarushi
tester: Sashiming
Ported in accordance with the HackerRank terms of service. Some parts have been modified.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。