問題一覧 > 通常問題

No.2546 Many Arithmetic Sequences

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 22
作問者 : Shirotsume / テスター : 👑 Nachia kaichou243
お気に入りにしたユーザー ProblemId : 9380 / 自分の提出
問題文最終更新日: 2023-11-15 16:42:33
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
yukicoder contest 413 (順位表) の他の問題:

Problem Statement

There are $N$ arithmetic sequences. The $i$-th arithmetic sequence has first term $A_i$, common difference $D_i$, and $10^{100}$ terms.

For a sequence of non-negative integers $X = (X_1, X_2, \dots, X_N)$ of length $N$ with sum $M$, the score $f(X)$ of $X$ is defined as follows.

  • $\displaystyle f(X) = \sum_{i = 1}^{N}$ (the sum of the first $X_i$ terms of the $i$-th arithmetic sequence)

Here, the sum of the first $0$ terms is defined to be $0$.

When you can freely choose a sequence of non-negative integers $X$ of length $N$ with sum $M$, find the maximum possible value of $f(X)$.

Constraints

  • All input values are integers.
  • $2 \leq N \leq 3 \times 10^5$
  • $1 \leq M \leq 3 \times 10^5$
  • $-10^7 \leq A_i, D_i \leq 10^7$

Input

The input is given from standard input in the following format.

$N$ $M$
$A_1$ $D_1$
$\vdots$
$A_N$ $D_N$

Output

Output the maximum value of $f(X)$. Under the constraints of this problem, it can be shown that the absolute value of the answer is less than $2^{63}$.

Sample

Sample 1
Input
3 5
1 2
-8 5
13 -7
Output
29

There are $3$ arithmetic sequences $(1, 3, 5, \dots), (-8, -3, 2, \dots), (13, 6, -1, \dots)$.

When $X = (4, 0, 1)$, the score is $29$, and this is optimal.

Sample 2
Input
2 10
-100 -100
-10 0
Output
-100

There are $2$ arithmetic sequences $(-100, -200, -300, \dots), (-10, -10, -10, \dots)$.

When $X = (0, 10)$, the score is $-100$, and this is optimal. Note that the score can take a negative value.

Sample 3
Input
5 2000
4005698 -1849641
3217860 -4274311
9504793 -3809644
-1590549 2314
2581917 -3604118
Output
1454884836

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