結果
| 問題 | No.2546 Many Arithmetic Sequences |
| ユーザー |
 kaichou243
|
| 提出日時 | 2023-08-18 11:50:46 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 92 ms / 2,000 ms |
| コード長 | 25,020 bytes |
| コンパイル時間 | 4,635 ms |
| コンパイル使用メモリ | 318,360 KB |
| 実行使用メモリ | 14,752 KB |
| 最終ジャッジ日時 | 2023-11-25 20:44:50 |
| 合計ジャッジ時間 | 7,794 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,548 KB |
| testcase_01 | AC | 2 ms
6,548 KB |
| testcase_02 | AC | 2 ms
6,548 KB |
| testcase_03 | AC | 52 ms
8,228 KB |
| testcase_04 | AC | 64 ms
8,100 KB |
| testcase_05 | AC | 62 ms
8,356 KB |
| testcase_06 | AC | 16 ms
6,548 KB |
| testcase_07 | AC | 30 ms
6,548 KB |
| testcase_08 | AC | 12 ms
6,548 KB |
| testcase_09 | AC | 18 ms
6,548 KB |
| testcase_10 | AC | 33 ms
6,548 KB |
| testcase_11 | AC | 34 ms
8,104 KB |
| testcase_12 | AC | 20 ms
6,548 KB |
| testcase_13 | AC | 47 ms
7,460 KB |
| testcase_14 | AC | 33 ms
8,104 KB |
| testcase_15 | AC | 11 ms
6,548 KB |
| testcase_16 | AC | 34 ms
8,104 KB |
| testcase_17 | AC | 60 ms
9,764 KB |
| testcase_18 | AC | 33 ms
6,548 KB |
| testcase_19 | AC | 42 ms
7,332 KB |
| testcase_20 | AC | 21 ms
6,548 KB |
| testcase_21 | AC | 33 ms
7,844 KB |
| testcase_22 | AC | 49 ms
7,972 KB |
| testcase_23 | AC | 90 ms
11,856 KB |
| testcase_24 | AC | 92 ms
11,856 KB |
| testcase_25 | AC | 92 ms
11,856 KB |
| testcase_26 | AC | 90 ms
11,856 KB |
| testcase_27 | AC | 91 ms
11,856 KB |
| testcase_28 | AC | 55 ms
14,752 KB |
| testcase_29 | AC | 55 ms
14,752 KB |
| testcase_30 | AC | 54 ms
14,752 KB |
| testcase_31 | AC | 55 ms
14,752 KB |
| testcase_32 | AC | 55 ms
14,752 KB |
| testcase_33 | AC | 2 ms
6,548 KB |
| testcase_34 | AC | 70 ms
11,212 KB |
| testcase_35 | AC | 2 ms
6,548 KB |
| testcase_36 | AC | 53 ms
11,344 KB |
| testcase_37 | AC | 2 ms
6,548 KB |
| testcase_38 | AC | 2 ms
6,548 KB |
ソースコード
#include<bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll=long long;
using P = pair<ll,ll>;
const long double PI=acos(-1);
const ll INF=1e18;
const int inf=1e9;
template< uint32_t mod, bool fast = false >
struct MontgomeryModInt {
using mint = MontgomeryModInt;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for(i32 i = 0; i < 4; i++) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(r * mod == 1, "invalid, r * mod != 1");
static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
u32 a;
MontgomeryModInt() : a{} {}
MontgomeryModInt(const i64 &x)
: a(reduce(u64(fast ? x : (x % mod + mod)) * n2)) {}
static constexpr u32 reduce(const u64 &b) {
return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32);
}
constexpr mint& operator+=(const mint &p) {
if(i32(a += p.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
constexpr mint& operator-=(const mint &p) {
if(i32(a -= p.a) < 0) a += 2 * mod;
return *this;
}
constexpr mint& operator*=(const mint &p) {
a = reduce(u64(a) * p.a);
return *this;
}
constexpr mint& operator/=(const mint &p) {
*this *= modinv(p);
return *this;
}
constexpr mint operator-() const { return mint() - *this; }
constexpr mint operator+(const mint &p) const { return mint(*this) += p; }
constexpr mint operator-(const mint &p) const { return mint(*this) -= p; }
constexpr mint operator*(const mint &p) const { return mint(*this) *= p; }
constexpr mint operator/(const mint &p) const { return mint(*this) /= p; }
constexpr bool operator==(const mint &p) const { return (a >= mod ? a - mod : a) == (p.a >= mod ? p.a - mod : p.a); }
constexpr bool operator!=(const mint &p) const { return (a >= mod ? a - mod : a) != (p.a >= mod ? p.a - mod : p.a); }
u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
friend constexpr MontgomeryModInt<mod> modpow(const MontgomeryModInt<mod> &x,u64 n) noexcept {
MontgomeryModInt<mod> ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend constexpr MontgomeryModInt<mod> modinv(const MontgomeryModInt<mod> &r) noexcept {
u64 a = r.get(), b = mod, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
return MontgomeryModInt<mod>(u);
}
friend ostream &operator<<(ostream &os, const mint &p) {
return os << p.get();
}
friend istream &operator>>(istream &is, mint &a) {
i64 t;
is >> t;
a = mint(t);
return is;
}
static constexpr u32 getmod() { return mod; }
};
//fast Input by yosupo
#include <unistd.h>
#include <algorithm>
#include <array>
#include <cassert>
#include <cctype>
#include <cstring>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>
namespace fastio{
/*
quote from yosupo's submission in Library Checker
*/
int bsr(unsigned int n) {
return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long n) {
return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long long n) {
return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n);
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned __int128 n) {
unsigned long long low = (unsigned long long)(n);
unsigned long long high = (unsigned long long)(n >> 64);
return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low);
}
namespace internal {
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value ||
internal::is_signed_int128<T>::value ||
internal::is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <class T>
using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
struct Scanner {
public:
Scanner(const Scanner&) = delete;
Scanner& operator=(const Scanner&) = delete;
Scanner(FILE* fp) : fd(fileno(fp)) {}
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
int read_unsafe() { return 0; }
template <class H, class... T> int read_unsafe(H& h, T&... t) {
bool f = read_single(h);
if (!f) return 0;
return 1 + read_unsafe(t...);
}
int close() { return ::close(fd); }
private:
static constexpr int SIZE = 1 << 15;
int fd = -1;
std::array<char, SIZE + 1> line;
int st = 0, ed = 0;
bool eof = false;
bool read_single(std::string& ref) {
if (!skip_space()) return false;
ref = "";
while (true) {
char c = top();
if (c <= ' ') break;
ref += c;
st++;
}
return true;
}
bool read_single(double& ref) {
std::string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
template <class T,
std::enable_if_t<std::is_same<T, char>::value>* = nullptr>
bool read_single(T& ref) {
if (!skip_space<50>()) return false;
ref = top();
st++;
return true;
}
template <class T,
internal::is_signed_int_t<T>* = nullptr,
std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>
bool read_single(T& sref) {
using U = internal::to_unsigned_t<T>;
if (!skip_space<50>()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
U ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
sref = neg ? -ref : ref;
return true;
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>
bool read_single(U& ref) {
if (!skip_space<50>()) return false;
ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
return true;
}
bool reread() {
if (ed - st >= 50) return true;
if (st > SIZE / 2) {
std::memmove(line.data(), line.data() + st, ed - st);
ed -= st;
st = 0;
}
if (eof) return false;
auto u = ::read(fd, line.data() + ed, SIZE - ed);
if (u == 0) {
eof = true;
line[ed] = '\0';
u = 1;
}
ed += int(u);
line[ed] = char(127);
return true;
}
char top() {
if (st == ed) {
bool f = reread();
assert(f);
}
return line[st];
}
template <int TOKEN_LEN = 0>
bool skip_space() {
while (true) {
while (line[st] <= ' ') st++;
if (ed - st > TOKEN_LEN) return true;
if (st > ed) st = ed;
for (auto i = st; i < ed; i++) {
if (line[i] <= ' ') return true;
}
if (!reread()) return false;
}
}
};
//fast Output by ei1333
/**
* @brief Printer(高速出力)
*/
struct Printer {
public:
explicit Printer(FILE *fp) : fp(fp) {}
~Printer() { flush(); }
template< bool f = false, typename T, typename... E >
void write(const T &t, const E &... e) {
if(f) write_single(' ');
write_single(t);
write< true >(e...);
}
template< typename... T >
void writeln(const T &...t) {
write(t...);
write_single('\n');
}
void flush() {
fwrite(line, 1, st - line, fp);
st = line;
}
private:
FILE *fp = nullptr;
static constexpr size_t line_size = 1 << 16;
static constexpr size_t int_digits = 20;
char line[line_size + 1] = {};
char small[32] = {};
char *st = line;
template< bool f = false >
void write() {}
void write_single(const char &t) {
if(st + 1 >= line + line_size) flush();
*st++ = t;
}
template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >
void write_single(T s) {
if(st + int_digits >= line + line_size) flush();
if(s == 0) {
write_single('0');
return;
}
if(s < 0) {
write_single('-');
s = -s;
}
char *mp = small + sizeof(small);
typename make_unsigned< T >::type y = s;
size_t len = 0;
while(y > 0) {
*--mp = y % 10 + '0';
y /= 10;
++len;
}
memmove(st, mp, len);
st += len;
}
void write_single(const string &s) {
for(auto &c : s) write_single(c);
}
void write_single(const char *s) {
while(*s != 0) write_single(*s++);
}
template< typename T >
void write_single(const vector< T > &s) {
for(size_t i = 0; i < s.size(); i++) {
if(i) write_single(' ');
write_single(s[i]);
}
}
};
}; //namespace fastio
using u64=unsigned long long;
u64 RNG_64() {
static uint64_t x_
= uint64_t(chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count())
* 10150724397891781847ULL;
x_ ^= x_ << 7;
return x_ ^= x_ >> 9;
}
u64 RNG(u64 lim) { return RNG_64() % lim; }
ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
struct modint61 {
static constexpr bool is_modint = true;
static constexpr ll mod = (1LL << 61) - 1;
ll val;
constexpr modint61(const ll x = 0) : val(x) {
while (val < 0) val += mod;
while (val >= mod) val -= mod;
}
bool operator<(const modint61 &other) const {
return val < other.val;
} // To use std::map
bool operator==(const modint61 &p) const { return val == p.val; }
bool operator!=(const modint61 &p) const { return val != p.val; }
modint61 &operator+=(const modint61 &p) {
if ((val += p.val) >= mod) val -= mod;
return *this;
}
modint61 &operator-=(const modint61 &p) {
if ((val += mod - p.val) >= mod) val -= mod;
return *this;
}
modint61 &operator*=(const modint61 &p) {
ll a = val, b = p.val;
const ll MASK30 = (1LL << 30) - 1;
const ll MASK31 = (1LL << 31) - 1;
const ll MASK61 = (1LL << 61) - 1;
ll au = a >> 31, ad = a & MASK31;
ll bu = b >> 31, bd = b & MASK31;
ll x = ad * bu + au * bd;
ll xu = x >> 30, xd = x & MASK30;
x = au * bu * 2 + xu + (xd << 31) + ad * bd;
xu = x >> 61, xd = x & MASK61;
x = xu + xd;
if (x >= MASK61) x -= MASK61;
val = x;
return *this;
}
modint61 operator-() const { return modint61(get_mod() - val); }
modint61 &operator/=(const modint61 &p) {
*this *= p.inverse();
return *this;
}
modint61 operator+(const modint61 &p) const { return modint61(*this) += p; }
modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; }
modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; }
modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; }
modint61 inverse() const {
ll a = val, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
return modint61(u);
}
modint61 pow(int64_t n) const {
modint61 ret(1), mul(val);
while (n > 0) {
if (n & 1) ret = ret * mul;
mul = mul * mul;
n >>= 1;
}
return ret;
}
static constexpr ll get_mod() { return mod; }
#ifdef FASTIO
void write() { fastio::printer.write(val); }
void read() { fastio::scanner.read(val); }
#endif
};
struct RollingHash {
using mint = modint61;
static constexpr u64 mod = mint::get_mod();
const mint base;
vector<mint> power;
static inline mint generate_base() { return RNG(mod); }
inline void expand(size_t sz) {
if (power.size() < sz + 1) {
int pre_sz = (int)power.size();
power.resize(sz + 1);
for(int i=pre_sz - 1;i<sz;i++) power[i + 1] = power[i] * base;
}
}
explicit RollingHash(mint base = generate_base()) : base(base), power{1} {}
template <typename STRING>
vector<mint> build(const STRING& s) const {
int sz = s.size();
vector<mint> hashed(sz + 1);
for (int i = 0; i < sz; i++) { hashed[i + 1] = hashed[i] * base + s[i]; }
return hashed;
}
mint query(const vector<mint>& s, int l, int r) {
expand(r - l);
return (s[r] - s[l] * power[r - l]).val;
}
mint combine(mint h1, mint h2, int h2len) {
expand(h2len);
return h1 * power[h2len] + h2;
}
mint add_char(mint h, int x) { return h * base + mint(x); }
int lcp(const vector<mint>& a, int l1, int r1, const vector<mint>& b, int l2,
int r2) {
int len = min(r1 - l1, r2 - l2);
int low = 0, high = len + 1;
while (high - low > 1) {
int mid = (low + high) / 2;
if (query(a, l1, l1 + mid) == query(b, l2, l2 + mid))
low = mid;
else
high = mid;
}
return low;
}
};
inline constexpr int msb(u64 x) {
int res = x ? 0 : -1;
if (x & 0xFFFFFFFF00000000) x &= 0xFFFFFFFF00000000, res += 32;
if (x & 0xFFFF0000FFFF0000) x &= 0xFFFF0000FFFF0000, res += 16;
if (x & 0xFF00FF00FF00FF00) x &= 0xFF00FF00FF00FF00, res += 8;
if (x & 0xF0F0F0F0F0F0F0F0) x &= 0xF0F0F0F0F0F0F0F0, res += 4;
if (x & 0xCCCCCCCCCCCCCCCC) x &= 0xCCCCCCCCCCCCCCCC, res += 2;
return res + ((x & 0xAAAAAAAAAAAAAAAA) ? 1 : 0);
}
inline constexpr int ceil_log2(u64 x) { return x ? msb(x - 1) + 1 : 0; }
template<class T> class infinity {
public:
static constexpr T value = std::numeric_limits<T>::max() / 2;
static constexpr T mvalue = std::numeric_limits<T>::min() / 2;
static constexpr T max = std::numeric_limits<T>::max();
static constexpr T min = std::numeric_limits<T>::min();
};
#if __cplusplus <= 201402L
template<class T> constexpr T infinity<T>::value;
template<class T> constexpr T infinity<T>::mvalue;
template<class T> constexpr T infinity<T>::max;
template<class T> constexpr T infinity<T>::min;
#endif
template<class T = ll, bool is_max = false> class LiChaoTree {
private:
struct Line {
T a, b;
int idx;
T get(T x) const { return a * x + b; }
Line() = default;
Line(T a, T b, int id) : a(a), b(b), idx(id) {}
};
int line_count = 0;
int ori, n;
std::vector<T> xs;
std::vector<Line> lns;
void add_line(int k, int a, int b, const Line& line) {
if (a + 1 == b) {
if (line.get(xs[a]) < lns[k].get(xs[a])) lns[k] = line;
return;
}
int m = (a + b) >> 1;
T x1 = lns[k].get(xs[a]), x2 = line.get(xs[a]);
T y1 = lns[k].get(xs[b - 1]), y2 = line.get(xs[b - 1]);
if (x1 <= x2 && y1 <= y2) return;
if (x2 <= x1 && y2 <= y1) {
lns[k] = line;
return;
}
if (lns[k].get(xs[m]) <= line.get(xs[m])) {
if (y1 < y2) add_line(k << 1, a, m, line);
else add_line(k << 1 | 1, m, b, line);
}
else {
if (y1 < y2) add_line(k << 1 | 1, m, b, lns[k]);
else add_line(k << 1, a, m, lns[k]);
lns[k] = line;
}
}
void add_segment(int k, int a, int b, int l, int r, const Line& line) {
if (l <= a && b <= r) {
add_line(k, a, b, line);
return;
}
if (r <= a || b <= l) return;
int m = (a + b) >> 1;
add_segment(k << 1, a, m, l, r, line);
add_segment(k << 1 | 1, m, b, l, r, line);
}
public:
LiChaoTree() : LiChaoTree({0}) {}
LiChaoTree(const std::vector<T>& xs_) { init(xs_); }
void init(const std::vector<T>& xs_) {
xs = xs_.empty() ? std::vector<T>{0} : xs_;
ori = xs.size();
n = 1 << ceil_log2(ori);
xs.reserve(n);
for(int i=xs_.size();i<n;i++) xs.push_back(xs_[i] + 1);
lns.assign(n << 1,
Line{0, is_max ? infinity<T>::min : infinity<T>::max, -1});
}
int add_segment(int l, int r, T x, T y) {
assert(0 <= l && l <= r && r <= ori);
add_segment(1, 0, n, l, r,
Line{is_max ? -x : x, is_max ? -y : y, line_count});
return line_count++;
}
int add_line(T x, T y) {
add_line(1, 0, n, Line{is_max ? -x : x, is_max ? -y : y, line_count});
return line_count++;
}
T get_min(int k) const {
int x = k + n;
T res = lns[x].get(xs[k]);
while (x >>= 1) {
const T y = lns[x].get(xs[k]);
if(is_max) chmin(res, -y );
else chmin(res, y);
}
return res;
}
struct line {
T a, b;
int idx;
};
line get_min_line(int k) const {
int x = k + n;
T mn = lns[x].get(xs[k]);
Line res = lns[x];
while (x >>= 1) {
const T y = lns[x].get(xs[k]);
if (chmin(mn, is_max ? -y : y)) res = lns[x];
}
return line{is_max ? -res.a : res.a, is_max ? -res.b : res.b, res.idx};
}
};
template<class T , bool is_max ,
class largeT>
class ConvexHullTrick {
private:
struct Line {
T a, b;
int idx;
bool is_query;
mutable ll nxt_a, nxt_b;
mutable bool has_nxt;
T get(T x) const { return a * x + b; }
T get_nxt(T x) const { return nxt_a * x + nxt_b; }
Line() = default;
Line(T a, T b, int id, bool i = false)
: a(a), b(b), idx(id), is_query(i), has_nxt(false) {}
friend bool operator<(const Line& lhs, const Line& rhs) {
assert(!lhs.is_query || !rhs.is_query);
if (lhs.is_query) {
if (!rhs.has_nxt) return true;
return rhs.get(lhs.a) < rhs.get_nxt(lhs.a);
}
if (rhs.is_query) {
if (!lhs.has_nxt) return false;
return lhs.get(rhs.a) > lhs.get_nxt(rhs.a);
}
return lhs.a == rhs.a ? lhs.b < rhs.b : lhs.a < rhs.a;
}
};
int line_count = 0;
std::set<Line> st;
bool is_necessary(const typename std::set<Line>::iterator& itr) {
if (itr != st.begin() && itr->a == prev(itr)->a)
return itr->b < prev(itr)->b;
if (itr != prev(st.end()) && itr->a == next(itr)->a)
return itr->b < next(itr)->b;
if (itr == st.begin() || itr == prev(st.end())) return true;
return static_cast<largeT>(itr->b - prev(itr)->b) *
static_cast<largeT>(next(itr)->a - itr->a) <
static_cast<largeT>(itr->b - next(itr)->b) *
static_cast<largeT>(prev(itr)->a - itr->a);
}
public:
ConvexHullTrick() = default;
int add_line(T a, T b) {
auto itr =
st.emplace(is_max ? -a : a, is_max ? -b : b, line_count).first;
if (!is_necessary(itr)) {
st.erase(itr);
return line_count++;
}
while (itr != st.begin() && !is_necessary(prev(itr)))
st.erase(prev(itr));
while (itr != prev(st.end()) && !is_necessary(next(itr)))
st.erase(next(itr));
if (itr != st.begin()) {
prev(itr)->has_nxt = true;
prev(itr)->nxt_a = itr->a;
prev(itr)->nxt_b = itr->b;
}
if (itr != prev(st.end())) {
itr->has_nxt = true;
itr->nxt_a = next(itr)->a;
itr->nxt_b = next(itr)->b;
}
else itr->has_nxt = false;
return line_count++;
}
struct line {
T a, b;
int idx;
};
line get_min_line(T x) const {
auto itr = st.lower_bound(Line{x, 0, -1, true});
Line res{*itr};
return line{is_max ? -res.a : res.a, is_max ? -res.b : res.b, res.idx};
}
T get_min(T x) const {
const auto& l = get_min_line(x);
return l.a * x + l.b;
}
bool empty() const { return st.empty(); }
};
using mint=MontgomeryModInt<998244353>;
int main(){
fastio::Scanner sc(stdin);
fastio::Printer pr(stdout);
#define in(...) sc.read(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define out(...) pr.write(__VA_ARGS__)
#define outln(...) pr.writeln(__VA_ARGS__)
#define outspace(...) pr.write(__VA_ARGS__),pr.write(' ')
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
/*
作問うまくない？
まあお気持ちとして公差が正のものと非正のものに分ける
正：
あえて他の数列を選ぶよりは一つで選び続けた方が良いので一つの数列からx項取ることだけ考えれば良い
max[i] x*(a+a+(x-1)d)/2が欲しいですよ
xに対して求めるときx/2は共通なのでmax[i]dx+2a-dが欲しいです→CHTですね
非正：
項が大きい方から取っていくのが最適
それぞれの項の一番前の項をpriqueに入れてpriqueで管理していけばとけますね
サンプル強くて助かる
*/
INT(n,m);
assert(2<=n&&n<=300000&&1<=m&&m<=300000);
ConvexHullTrick<ll,true,ll> cht;
priority_queue<pair<ll,ll>> pq;
bool plus=false,non_plus=false;;
FOR(i,n){
LL(a,d);
assert(-10000000<=a&&-10000000<=d&&10000000>=a&&10000000>=d);
if(d>0){
cht.add_line(d,2*a-d);
plus=true;
}else{
pq.push(make_pair(a,d));
non_plus=true;
}
}
vector<ll> s(m+1),t(m+1);
for(int i=0;i<=m;i++){
s[i]=cht.get_min(i)*i/2;
}
ll sum=0;
for(int i=0;i<=m;i++){
if(pq.empty()) break;
t[i]=sum;
auto [v,d]=pq.top();
pq.pop();
sum+=v;
pq.push(make_pair(v+d,d));
}
ll ans=-INF;
if(!plus){
ans=t[m];
}
if(!non_plus){
ans=s[m];
}
if(plus&&non_plus){
for(int i=0;i<=m;i++){
ans=max(ans,s[i]+t[m-i]);
}
}
outln(ans);
}