問題一覧 > 通常問題

No.1495 パンの仕入れ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : penguinmanpenguinman / テスター : akakimidoriakakimidori kaagekaage
2 ProblemId : 6189 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-10 07:04:00

問題文

ペンギン学園の学長である penguinman は、生徒達のためにパンを幾つか仕入れ、購買部で売ることにしました。

仕入れられるパンは N 種類あり、penguinman はその中からちょうど K 個を仕入れて売ります。同じ種類のパンを幾つ仕入れても構いませんし、1 つも仕入れないパンがあっても良いです。

仕入れにあたって生徒達にアンケートを取ったところ、M 個の回答が得られ、i (1iM) 個目の回答は以下のものでした。

  • xi 種類目のパンをちょうど yi 個仕入れて欲しい。

penguinman は生徒達の要望に出来る限り答えたいです。Bii 種類目のパンの仕入れ数とした時、適切にパンを仕入れることで i=1M(Bxiyi)2 を最小化してください。

Bi はパンの仕入れ数であるため非負整数である必要があり、また先述の条件より Bi の総和は K になる必要があります。この問題の制約下では解は 1018 以下に収まります。

T 個のテストケースに答えてください。

入力

入力の 1 行目は以下の通りです。

T

続いて T 個のテストケースが以下のフォーマットで順番に与えられます。

N M K
x1 y1
x2 y2

xM yM

  • 1T100
  • 1N, M2×105
  • 1K109
  • 1xiN
  • 1yi109
  • M×max(K, max(y))21018
  • T 個のテストケース全体における N, M の総和はそれぞれ 2×105 を超えない
  • 入力は全て整数

出力

T 行に渡って出力してください。k 行目には k 個目のテストケースにおける i=1M(Bxiyi)2 の最小値を出力してください。

サンプル

サンプル1
入力
2
2 2 3
1 1
2 2
3 4 10
1 4
2 3
1 4
2 4
出力
0
1

1 つ目のテストケースでは、B1=1, B2=2 とするべきです。

2 つ目のテストケースでは、B1=4, B2=3, B3=3 とするか、或いは B1=4, B2=4, B3=2 とするべきです。

サンプル2
入力
3
5 8 93
2 11
3 80
3 58
1 78
4 8
4 71
1 39
2 30
6 10 56
5 31
1 48
6 8
2 24
4 75
2 83
5 80
5 31
4 60
2 63
6 10 480
5 74
3 64
5 40
3 52
2 98
2 83
2 5
6 53
6 41
2 88
出力
7659
17317
6216

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