結果
| 問題 | No.3684 chokudai_niku.png |
| コンテスト | |
| ユーザー |
 yesantikiss
|
| 提出日時 | 2026-09-05 13:07:36 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 23 ms / 2,000 ms |
| + 987µs | |
| コード長 | 32,311 bytes |
| 記録 | |
| コンパイル時間 | 4,482 ms |
| コンパイル使用メモリ | 389,804 KB |
| 実行使用メモリ | 8,320 KB |
| 最終ジャッジ日時 | 2026-09-05 13:08:22 |
| 合計ジャッジ時間 | 10,576 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 44 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
#include <chrono>
// Library : https://yesantikiss.github.io/cp-library/
// BEGIN cp-library: algo/binary_search.hpp
namespace yesantikiss {
// [left, right) の範囲で f(mid) が true になる最小の left を返す
// 単調性: false...false,true...true
template<class F, class T>
T binary_search_min_left(T left, T right, F f){
while (right - left > 1){
T mid = left + (right - left) / 2;
if(f(mid)) right = mid;
else left = mid;
}
return right;
}
// [left, right) の範囲で f(mid) が true になる最大の right-1 を返す
// 単調性: true...true,false...false
template<class F, class T>
T binary_search_max_right(T left, T right, F f){
while (right - left > 1){
T mid = left + (right - left) / 2;
if(f(mid)) left = mid;
else right = mid;
}
return left;
}
}
// END cp-library: algo/binary_search.hpp
// BEGIN cp-library: utils/fraction.hpp
#include <cstddef>
#include <ios>
#include <istream>
#include <limits>
#include <ostream>
#include <stdexcept>
#include <string>
#include <type_traits>
namespace yesantikiss {
namespace fraction_detail {
using i128 = __int128;
using u128 = unsigned __int128;
template<class T>
inline constexpr bool is_supported_integer_v =
(std::is_integral_v<T> && std::is_signed_v<T> &&
!std::is_same_v<T, bool>) ||
std::is_same_v<T, i128>;
struct u256 {
u128 hi = 0;
u128 lo = 0;
};
inline bool is_zero(const u256& x) {
return x.hi == 0 && x.lo == 0;
}
inline int compare(const u256& a, const u256& b) {
if (a.hi != b.hi) return a.hi < b.hi ? -1 : 1;
if (a.lo != b.lo) return a.lo < b.lo ? -1 : 1;
return 0;
}
inline u256 add(const u256& a, const u256& b) {
u256 res;
res.lo = a.lo + b.lo;
res.hi = a.hi + b.hi + (res.lo < a.lo);
return res;
}
// a >= b を仮定する。
inline u256 subtract(const u256& a, const u256& b) {
u256 res;
res.lo = a.lo - b.lo;
res.hi = a.hi - b.hi - (a.lo < b.lo);
return res;
}
inline u256 multiply(u128 a, u128 b) {
constexpr u128 mask64 = (u128(1) << 64) - 1;
u128 a0 = a & mask64;
u128 a1 = a >> 64;
u128 b0 = b & mask64;
u128 b1 = b >> 64;
u128 p00 = a0 * b0;
u128 p01 = a0 * b1;
u128 p10 = a1 * b0;
u128 p11 = a1 * b1;
u128 lo = p00;
u128 x = p01 << 64;
u128 next = lo + x;
u128 carry = next < lo;
lo = next;
x = p10 << 64;
next = lo + x;
carry += next < lo;
lo = next;
u128 hi = p11 + (p01 >> 64) + (p10 >> 64) + carry;
return {hi, lo};
}
inline u256 from_u128(u128 x) {
return {0, x};
}
struct div_result {
u256 quotient;
u128 remainder;
};
inline div_result divide(const u256& value, u128 divisor) {
if (divisor == 0) {
throw std::domain_error("fraction: division by zero");
}
if (value.hi == 0) {
return {{0, value.lo / divisor}, value.lo % divisor};
}
u256 quotient;
u128 remainder = 0;
for (int bit_index = 255; bit_index >= 0; --bit_index) {
u128 bit;
if (bit_index >= 128) {
bit = (value.hi >> (bit_index - 128)) & 1;
} else {
bit = (value.lo >> bit_index) & 1;
}
bool carry = (remainder >> 127) != 0;
remainder = (remainder << 1) | bit;
if (carry || remainder >= divisor) {
remainder -= divisor;
if (bit_index >= 128) {
quotient.hi |= u128(1) << (bit_index - 128);
} else {
quotient.lo |= u128(1) << bit_index;
}
}
}
return {quotient, remainder};
}
inline u128 modulo(const u256& value, u128 divisor) {
return divide(value, divisor).remainder;
}
inline u256 divide_exact(const u256& value, u128 divisor) {
if (divisor == 1) return value;
div_result result = divide(value, divisor);
if (result.remainder != 0) {
throw std::logic_error("fraction: internal non-exact division");
}
return result.quotient;
}
inline u128 gcd(u128 a, u128 b) {
while (b != 0) {
u128 r = a % b;
a = b;
b = r;
}
return a;
}
struct signed_u256 {
bool negative = false;
u256 magnitude;
};
inline signed_u256 add(const signed_u256& a, const signed_u256& b) {
if (a.negative == b.negative) {
signed_u256 res{a.negative, add(a.magnitude, b.magnitude)};
if (is_zero(res.magnitude)) res.negative = false;
return res;
}
int cmp = compare(a.magnitude, b.magnitude);
if (cmp == 0) return {};
if (cmp > 0) {
return {a.negative, subtract(a.magnitude, b.magnitude)};
}
return {b.negative, subtract(b.magnitude, a.magnitude)};
}
}
// T は符号付き整数型（最大 __int128）。常に既約かつ den > 0 に保つ。
// 正規化後の値が T に収まらない演算は std::overflow_error を送出する。
template<class T>
struct fraction {
static_assert(
fraction_detail::is_supported_integer_v<T>,
"fraction<T>: T must be a signed integral type");
static_assert(
sizeof(T) <= sizeof(fraction_detail::i128),
"fraction<T>: integers wider than 128 bits are not supported");
using u128 = fraction_detail::u128;
using u256 = fraction_detail::u256;
using signed_u256 = fraction_detail::signed_u256;
T num, den; // den > 0 を常に保つ
fraction() : num(0), den(1) {}
fraction(T n) : num(n), den(1) {}
fraction(T n, T d) {
if (d == 0) {
throw std::invalid_argument(
"fraction: denominator must not be zero");
}
bool negative = (n < 0) != (d < 0);
assign_normalized(
negative, magnitude(n), magnitude(d));
}
private:
static constexpr u128 max_u128() {
return ~u128(0);
}
static constexpr u128 max_magnitude() {
return static_cast<u128>(std::numeric_limits<T>::max());
}
static constexpr u128 min_magnitude() {
return max_magnitude() + 1;
}
static u128 magnitude(T x) {
u128 value = static_cast<u128>(x);
return x < 0 ? u128(0) - value : value;
}
static bool fits(bool negative, u128 value) {
return value <= (negative ? min_magnitude() : max_magnitude());
}
static T from_magnitude(bool negative, u128 value) {
if (!fits(negative, value)) {
throw std::overflow_error(
"fraction: value does not fit the storage type");
}
if (!negative) return static_cast<T>(value);
if (value == min_magnitude()) {
return std::numeric_limits<T>::min();
}
return -static_cast<T>(value);
}
void assign_reduced(
bool negative, const u256& numerator, const u256& denominator) {
if (fraction_detail::is_zero(denominator)) {
throw std::invalid_argument(
"fraction: denominator must not be zero");
}
if (fraction_detail::is_zero(numerator)) {
num = 0;
den = 1;
return;
}
if (numerator.hi != 0 || denominator.hi != 0 ||
!fits(negative, numerator.lo) ||
denominator.lo > max_magnitude()) {
throw std::overflow_error(
"fraction: result does not fit the storage type");
}
num = from_magnitude(negative, numerator.lo);
den = static_cast<T>(denominator.lo);
}
bool try_assign_reduced(
bool negative, const u256& numerator, const u256& denominator) {
if (fraction_detail::is_zero(denominator)) return false;
if (fraction_detail::is_zero(numerator)) {
num = 0;
den = 1;
return true;
}
if (numerator.hi != 0 || denominator.hi != 0 ||
!fits(negative, numerator.lo) ||
denominator.lo > max_magnitude()) {
return false;
}
num = from_magnitude(negative, numerator.lo);
den = static_cast<T>(denominator.lo);
return true;
}
void assign_normalized(bool negative, u128 numerator, u128 denominator) {
if (numerator == 0) {
num = 0;
den = 1;
return;
}
u128 g = fraction_detail::gcd(numerator, denominator);
assign_reduced(
negative,
fraction_detail::from_u128(numerator / g),
fraction_detail::from_u128(denominator / g));
}
bool try_assign_normalized(
bool negative, u128 numerator, u128 denominator) {
if (denominator == 0) return false;
if (numerator == 0) {
num = 0;
den = 1;
return true;
}
u128 g = fraction_detail::gcd(numerator, denominator);
return try_assign_reduced(
negative,
fraction_detail::from_u128(numerator / g),
fraction_detail::from_u128(denominator / g));
}
static signed_u256 signed_product(T value, u128 multiplier) {
u256 product =
fraction_detail::multiply(magnitude(value), multiplier);
return {
value < 0 && !fraction_detail::is_zero(product),
product
};
}
fraction& add_or_subtract(const fraction& other, bool subtract) {
u128 b = static_cast<u128>(den);
u128 d = static_cast<u128>(other.den);
u128 common = fraction_detail::gcd(b, d);
u128 b_reduced = b / common;
u128 d_reduced = d / common;
signed_u256 left = signed_product(num, d_reduced);
signed_u256 right = signed_product(other.num, b_reduced);
if (subtract && !fraction_detail::is_zero(right.magnitude)) {
right.negative = !right.negative;
}
signed_u256 numerator = fraction_detail::add(left, right);
if (fraction_detail::is_zero(numerator.magnitude)) {
num = 0;
den = 1;
return *this;
}
u128 remainder =
fraction_detail::modulo(numerator.magnitude, common);
u128 reduction = fraction_detail::gcd(remainder, common);
u256 reduced_numerator =
fraction_detail::divide_exact(
numerator.magnitude, reduction);
u256 reduced_denominator =
fraction_detail::multiply(
b_reduced, d / reduction);
assign_reduced(
numerator.negative,
reduced_numerator,
reduced_denominator);
return *this;
}
static bool parse_unsigned(
const std::string& s, std::size_t first, std::size_t last,
u128 limit, u128& out) {
if (first == last) return false;
u128 value = 0;
for (std::size_t i = first; i < last; ++i) {
char c = s[i];
if (c < '0' || c > '9') return false;
u128 digit = static_cast<unsigned>(c - '0');
if (digit > limit ||
value > (limit - digit) / 10) {
return false;
}
value = value * 10 + digit;
}
out = value;
return true;
}
static bool pow10(std::size_t exponent, u128& out) {
u128 value = 1;
for (std::size_t i = 0; i < exponent; ++i) {
if (value > max_u128() / 10) return false;
value *= 10;
}
out = value;
return true;
}
static std::ostream& write_integer(std::ostream& os, T value) {
u128 x = magnitude(value);
if (value < 0) os.put('-');
char digits[40];
int size = 0;
do {
digits[size++] = static_cast<char>('0' + x % 10);
x /= 10;
} while (x != 0);
while (size > 0) os.put(digits[--size]);
return os;
}
public:
fraction operator-() const {
fraction result;
result.assign_reduced(
num >= 0,
fraction_detail::from_u128(magnitude(num)),
fraction_detail::from_u128(
static_cast<u128>(den)));
return result;
}
fraction inv() const {
if (num == 0) {
throw std::domain_error(
"fraction: zero has no reciprocal");
}
fraction result;
result.assign_normalized(
num < 0,
static_cast<u128>(den),
magnitude(num));
return result;
}
bool is_integer() const {
return den == 1;
}
long double to_ld() const {
return static_cast<long double>(num) /
static_cast<long double>(den);
}
double to_double() const {
return static_cast<double>(num) /
static_cast<double>(den);
}
T floor() const {
u128 n = magnitude(num);
u128 d = static_cast<u128>(den);
u128 quotient = n / d;
u128 remainder = n % d;
if (num >= 0) return from_magnitude(false, quotient);
return from_magnitude(true, quotient + (remainder != 0));
}
T ceil() const {
u128 n = magnitude(num);
u128 d = static_cast<u128>(den);
u128 quotient = n / d;
u128 remainder = n % d;
if (num >= 0) {
return from_magnitude(
false, quotient + (remainder != 0));
}
return from_magnitude(true, quotient);
}
fraction& operator+=(const fraction& other) {
return add_or_subtract(other, false);
}
fraction& operator-=(const fraction& other) {
return add_or_subtract(other, true);
}
fraction& operator*=(const fraction& other) {
if (num == 0 || other.num == 0) {
num = 0;
den = 1;
return *this;
}
u128 a = magnitude(num);
u128 b = static_cast<u128>(den);
u128 c = magnitude(other.num);
u128 d = static_cast<u128>(other.den);
u128 left_reduction = fraction_detail::gcd(a, d);
u128 right_reduction = fraction_detail::gcd(c, b);
u256 numerator = fraction_detail::multiply(
a / left_reduction, c / right_reduction);
u256 denominator = fraction_detail::multiply(
b / right_reduction, d / left_reduction);
assign_reduced(
(num < 0) != (other.num < 0),
numerator,
denominator);
return *this;
}
fraction& operator/=(const fraction& other) {
if (other.num == 0) {
throw std::domain_error(
"fraction: division by zero");
}
if (num == 0) {
den = 1;
return *this;
}
u128 a = magnitude(num);
u128 b = static_cast<u128>(den);
u128 c = magnitude(other.num);
u128 d = static_cast<u128>(other.den);
u128 numerator_reduction = fraction_detail::gcd(a, c);
u128 denominator_reduction = fraction_detail::gcd(d, b);
u256 numerator = fraction_detail::multiply(
a / numerator_reduction,
d / denominator_reduction);
u256 denominator = fraction_detail::multiply(
b / denominator_reduction,
c / numerator_reduction);
assign_reduced(
(num < 0) != (other.num < 0),
numerator,
denominator);
return *this;
}
friend fraction operator+(fraction a, const fraction& b) {
a += b;
return a;
}
friend fraction operator-(fraction a, const fraction& b) {
a -= b;
return a;
}
friend fraction operator*(fraction a, const fraction& b) {
a *= b;
return a;
}
friend fraction operator/(fraction a, const fraction& b) {
a /= b;
return a;
}
friend bool operator==(const fraction& a, const fraction& b) {
return a.num == b.num && a.den == b.den;
}
friend bool operator!=(const fraction& a, const fraction& b) {
return !(a == b);
}
friend bool operator<(const fraction& a, const fraction& b) {
if ((a.num < 0) != (b.num < 0)) return a.num < 0;
u256 left = fraction_detail::multiply(
magnitude(a.num), static_cast<u128>(b.den));
u256 right = fraction_detail::multiply(
magnitude(b.num), static_cast<u128>(a.den));
int cmp = fraction_detail::compare(left, right);
return a.num < 0 ? cmp > 0 : cmp < 0;
}
friend bool operator>(const fraction& a, const fraction& b) {
return b < a;
}
friend bool operator<=(const fraction& a, const fraction& b) {
return !(b < a);
}
friend bool operator>=(const fraction& a, const fraction& b) {
return !(a < b);
}
// 対応形式: 12, -7, 1.5, .5, 1., 3/4, -10/6
static bool parse(const std::string& s, fraction& out) {
if (s.empty()) return false;
bool negative = false;
std::size_t first = 0;
if (s[first] == '+') {
++first;
} else if (s[first] == '-') {
negative = true;
++first;
}
if (first == s.size()) return false;
std::size_t slash = s.find('/', first);
if (slash != std::string::npos) {
if (s.find('/', slash + 1) != std::string::npos) return false;
u128 numerator;
u128 denominator;
if (!parse_unsigned(
s, first, slash, max_u128(), numerator) ||
!parse_unsigned(
s, slash + 1, s.size(),
max_u128(), denominator) ||
denominator == 0) {
return false;
}
fraction tmp;
if (!tmp.try_assign_normalized(
negative, numerator, denominator)) {
return false;
}
out = tmp;
return true;
}
std::size_t dot = s.find('.', first);
if (dot == std::string::npos) {
u128 numerator;
if (!parse_unsigned(
s, first, s.size(), max_u128(), numerator)) {
return false;
}
fraction tmp;
if (!tmp.try_assign_normalized(
negative, numerator, 1)) {
return false;
}
out = tmp;
return true;
}
if (s.find('.', dot + 1) != std::string::npos) return false;
if (first == dot && dot + 1 == s.size()) return false;
std::size_t fractional_end = s.size();
while (fractional_end > dot + 1 &&
s[fractional_end - 1] == '0') {
--fractional_end;
}
u128 integer_part = 0;
if (first != dot &&
!parse_unsigned(
s, first, dot, max_u128(), integer_part)) {
return false;
}
std::size_t fractional_digits = fractional_end - (dot + 1);
u128 denominator;
if (!pow10(fractional_digits, denominator)) return false;
u128 fractional_part = 0;
if (fractional_digits != 0 &&
!parse_unsigned(
s, dot + 1, fractional_end,
denominator - 1, fractional_part)) {
return false;
}
u256 numerator = fraction_detail::add(
fraction_detail::multiply(integer_part, denominator),
fraction_detail::from_u128(fractional_part));
if (fraction_detail::is_zero(numerator)) {
out = fraction();
return true;
}
u128 reduction = fraction_detail::gcd(
fraction_detail::modulo(numerator, denominator),
denominator);
numerator =
fraction_detail::divide_exact(numerator, reduction);
u128 reduced_denominator = denominator / reduction;
fraction tmp;
if (!tmp.try_assign_reduced(
negative,
numerator,
fraction_detail::from_u128(reduced_denominator))) {
return false;
}
out = tmp;
return true;
}
friend std::ostream& operator<<(
std::ostream& os, const fraction& x) {
write_integer(os, x.num);
if (x.den != 1) {
os.put('/');
write_integer(os, x.den);
}
return os;
}
friend std::istream& operator>>(
std::istream& is, fraction& x) {
std::string s;
is >> s;
if (!is) return is;
fraction tmp;
if (!fraction::parse(s, tmp)) {
is.setstate(std::ios::failbit);
return is;
}
x = tmp;
return is;
}
};
template<class T>
fraction<T> abs(const fraction<T>& x) {
return x.num < 0 ? -x : x;
}
using fr = fraction<__int128>;
}
// END cp-library: utils/fraction.hpp
// BEGIN cp-library: utils/hash.hpp
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <utility>
namespace yesantikiss {
namespace hash_detail {
inline std::uint64_t splitmix64(std::uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
inline std::uint64_t random_seed() {
static const std::uint64_t seed =
static_cast<std::uint64_t>(
std::chrono::steady_clock::now()
.time_since_epoch()
.count());
return seed;
}
}
struct custom_hash {
template<class T>
std::size_t operator()(const T& value) const {
return static_cast<std::size_t>(hash_detail::splitmix64(
static_cast<std::uint64_t>(std::hash<T>{}(value)) +
hash_detail::random_seed()));
}
template<class T, class U>
std::size_t operator()(const std::pair<T, U>& value) const {
std::uint64_t first =
static_cast<std::uint64_t>((*this)(value.first));
std::uint64_t second =
static_cast<std::uint64_t>((*this)(value.second));
return static_cast<std::size_t>(hash_detail::splitmix64(
first ^ (second + 0x9e3779b97f4a7c15ULL +
(first << 6) + (first >> 2))));
}
};
template<
class Key,
class T,
class Hash = custom_hash,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>>
using umap =
std::unordered_map<Key, T, Hash, KeyEqual, Allocator>;
template<
class Key,
class Hash = custom_hash,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<Key>>
using uset =
std::unordered_set<Key, Hash, KeyEqual, Allocator>;
}
// END cp-library: utils/hash.hpp
// BEGIN cp-library: utils/int128.hpp
#include <ios>
#include <istream>
#include <ostream>
#include <string>
namespace yesantikiss {
using i128 = __int128;
using u128 = unsigned __int128;
using int128 = __int128;
namespace int128_detail {
inline std::string to_string(u128 value) {
char digits[39];
int size = 0;
do {
digits[size++] =
static_cast<char>('0' + static_cast<int>(value % 10));
value /= 10;
} while (value != 0);
std::string result;
result.reserve(static_cast<std::size_t>(size));
while (size > 0) result.push_back(digits[--size]);
return result;
}
inline bool parse_magnitude(
const std::string& token, std::size_t first, u128 limit,
u128& result) {
if (first == token.size()) return false;
u128 value = 0;
for (std::size_t i = first; i < token.size(); ++i) {
char c = token[i];
if (c < '0' || c > '9') return false;
u128 digit = static_cast<unsigned>(c - '0');
if (digit > limit || value > (limit - digit) / 10) {
return false;
}
value = value * 10 + digit;
}
result = value;
return true;
}
}
}
inline std::ostream& operator<<(std::ostream& os, yesantikiss::i128 value) {
yesantikiss::u128 magnitude = static_cast<yesantikiss::u128>(value);
if (value < 0) {
magnitude = yesantikiss::u128(0) - magnitude;
}
std::string result =
yesantikiss::int128_detail::to_string(magnitude);
if (value < 0) result.insert(result.begin(), '-');
return os << result;
}
inline std::ostream& operator<<(std::ostream& os, yesantikiss::u128 value) {
return os << yesantikiss::int128_detail::to_string(value);
}
inline std::istream& operator>>(std::istream& is, yesantikiss::i128& value) {
std::string token;
if (!(is >> token)) return is;
std::size_t first = 0;
bool negative = false;
if (token[first] == '+' || token[first] == '-') {
negative = token[first] == '-';
++first;
}
constexpr yesantikiss::u128 min_magnitude =
yesantikiss::u128(1) << 127;
constexpr yesantikiss::u128 max_magnitude = min_magnitude - 1;
yesantikiss::u128 magnitude;
if (!yesantikiss::int128_detail::parse_magnitude(
token, first,
negative ? min_magnitude : max_magnitude, magnitude)) {
is.setstate(std::ios::failbit);
return is;
}
if (!negative) {
value = static_cast<yesantikiss::i128>(magnitude);
} else if (magnitude == min_magnitude) {
value = -static_cast<yesantikiss::i128>(magnitude - 1) - 1;
} else {
value = -static_cast<yesantikiss::i128>(magnitude);
}
return is;
}
inline std::istream& operator>>(std::istream& is, yesantikiss::u128& value) {
std::string token;
if (!(is >> token)) return is;
std::size_t first = 0;
if (token[first] == '+') ++first;
if (first == token.size() || token[first] == '-') {
is.setstate(std::ios::failbit);
return is;
}
constexpr yesantikiss::u128 max_value = ~yesantikiss::u128(0);
yesantikiss::u128 parsed;
if (!yesantikiss::int128_detail::parse_magnitude(
token, first, max_value, parsed)) {
is.setstate(std::ios::failbit);
return is;
}
value = parsed;
return is;
}
// END cp-library: utils/int128.hpp
#ifdef LOCAL
#else
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
using namespace atcoder;
using namespace std;
//using namespace yesantikiss;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define rep_2(i, j, n) for (ll i = 0; i < (n); ++i) for (ll j = i + 1; j < (n); ++j)
#define foreach(i, n) for (auto& i : (n))
template<typename T, typename U> inline bool chmax(T &a, U b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T, typename U> inline bool chmin(T &a, U b) { return ((a > b) ? (a = b, true) : (false)); }
#define popcount __builtin_popcountll
#define bitcheck(mask, j) ((mask) & (1LL << (j)))
#define yesno(t) (t) ? cout << "Yes\n" : cout << "No\n"
int msb(int n) {
return 31 - __builtin_clz(n);
}
int msb(ll n) {
return 63 - __builtin_clzll(n);
}
using mint = modint998244353;
using mint1 = modint1000000007;
template <typename T>
using v = vector<T>;
template <typename T>
using vv = v<v<T>>;
template <typename T>
using vvv = vv<v<T>>;
template <typename T, typename U>
using P = pair<T, U>;
using grid = vector<vector<char>>;
using graph = vector<vector<int>>;
using vi = vector<int>; using vvi = vector<vector<int>>; using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>; using vvl = vector<vector<ll>>; using vvvl = vector<vector<vector<ll>>>;
using vm = vector<mint>; using vvm = vector<vector<mint>>; using vvvm = vector<vector<vector<mint>>>;
using vm1 = vector<mint1>; using vvm1 = vector<vector<mint1>>; using vvvm1 = vector<vector<vector<mint1>>>;
using vld = vector<ld>; using vvld = vector<vector<ld>>; using vvvld = vector<vector<vector<ld>>>;
using vb = vector<bool>; using vvb = vector<vector<bool>>; using vvvb = vector<vector<vector<bool>>>;
using vs = vector<string>; using vvs = vector<vector<string>>;
using vc = vector<char>; using vvc = vector<vector<char>>;
ll inf = 4e18;
void zikken() {
// ここに実験を書く
cout << "--- zikken ---\n";
exit(0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 困ったら実験！！！！！！！！！！
// ランテスもやる
// zikken();
ll n, m;
cin >> n >> m;
vl a(n), b(n);
rep(i, n) cin >> a[i];
rep(i, n) cin >> b[i];
ll ans = 0;
vl sum(n + 1, 0);
rep(i, n) sum[i + 1] = sum[i] + max(0LL, a[i] - b[i]);
rep(i, n - m + 1) chmax(ans, sum[i + m] - sum[i]);
cout << ans << '\n';
return 0;
}