結果
| 問題 | No.1037 exhausted |
| ユーザー |
 43flyingcar
|
| 提出日時 | 2020-06-06 22:03:34 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,314 ms / 2,000 ms |
| コード長 | 32,823 bytes |
| コンパイル時間 | 13,544 ms |
| コンパイル使用メモリ | 392,236 KB |
| 実行使用メモリ | 55,240 KB |
| 最終ジャッジ日時 | 2024-06-06 03:02:00 |
| 合計ジャッジ時間 | 23,311 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 1 ms
6,940 KB |
| testcase_03 | AC | 1 ms
6,940 KB |
| testcase_04 | AC | 1 ms
6,948 KB |
| testcase_05 | AC | 0 ms
6,940 KB |
| testcase_06 | AC | 1 ms
6,944 KB |
| testcase_07 | AC | 1 ms
6,940 KB |
| testcase_08 | AC | 1 ms
6,944 KB |
| testcase_09 | AC | 1 ms
6,944 KB |
| testcase_10 | AC | 1 ms
6,944 KB |
| testcase_11 | AC | 0 ms
6,940 KB |
| testcase_12 | AC | 982 ms
50,232 KB |
| testcase_13 | AC | 798 ms
45,088 KB |
| testcase_14 | AC | 1,203 ms
54,208 KB |
| testcase_15 | AC | 941 ms
48,944 KB |
| testcase_16 | AC | 1,205 ms
53,340 KB |
| testcase_17 | AC | 1,230 ms
54,552 KB |
| testcase_18 | AC | 1,229 ms
52,880 KB |
| testcase_19 | AC | 1,314 ms
55,240 KB |
| testcase_20 | AC | 26 ms
33,152 KB |
| testcase_21 | AC | 26 ms
33,280 KB |
| testcase_22 | AC | 25 ms
33,152 KB |
コンパイルメッセージ
warning: unused import: `std::cmp::min`
--> src/main.rs:63:5
|
63 | use std::cmp::min;
| ^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `std::collections::BTreeMap`
--> src/main.rs:64:5
|
64 | use std::collections::BTreeMap;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::process`
--> src/main.rs:65:5
|
65 | use std::process;
| ^^^^^^^^^^^^
warning: unused import: `std::collections::HashSet`
--> src/main.rs:68:5
|
68 | use std::collections::HashSet;
| ^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::collections::BTreeSet`
--> src/main.rs:70:5
|
70 | use std::collections::BTreeSet;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unnecessary parentheses around `while` condition
--> src/main.rs:287:10
|
287 | while(n>0){
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
287 - while(n>0){
287 + while n>0 {
|
warning: unnecessary parentheses around `if` condition
--> src/main.rs:332:11
|
332 | if(self.par[x] == x){
| ^ ^
|
help: remove these parentheses
|
332 - if(self.par[x] == x){
332 + if self.par[x] == x {
|
warning: unnecessary parentheses around `if` condition
--> src/main.rs:349:16
|
349 | if (self.rank[x] < self.rank[y]){
| ^ ^
|
help: remove these parentheses
|
349 - if (self.rank[x] < self.rank[y]){
349 + if self.rank[x] < self.rank[y] {
|
warning: unnecessary parentheses around `if` condition
--> src/main.rs:360:19
|
360 | if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;}
| ^ ^
|
help: remove these parentheses
|
360 - if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;}
360 +
ソースコード
#[allow(unused_macros)]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! input_inner {
($next:expr) => {};
($next:expr, ) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let mut $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => {
( $(read_value!($next, $t)),* )
};
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, bytes) => {
read_value!($next, String).into_bytes()
};
($next:expr, usize1) => {
read_value!($next, usize) - 1
};
($next:expr, $t:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
use std::cmp::Ordering;
use std::cmp;
use std::cmp::min;
use std::collections::BTreeMap;
use std::process;
use std::cmp::Ord;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::mem;
use std::collections::BinaryHeap;
use std::hash::{Hash, Hasher};
// ---------- begin ModInt ----------
#[derive(Clone, Copy)]
struct ModInt(usize);
impl std::ops::Add for ModInt {
type Output = ModInt;
fn add(self, rhs: ModInt) -> Self::Output {
let mut d = self.0 + rhs.0;
if d >= MODu {
d -= MODu;
}
ModInt(d)
}
}
impl std::ops::AddAssign for ModInt {
fn add_assign(&mut self, rhs: ModInt) {
*self = *self + rhs;
}
}
impl std::ops::Sub for ModInt {
type Output = ModInt;
fn sub(self, rhs: ModInt) -> Self::Output {
let mut d = self.0 + MODu - rhs.0;
if d >= MODu {
d -= MODu;
}
ModInt(d)
}
}
impl std::ops::SubAssign for ModInt {
fn sub_assign(&mut self, rhs: ModInt) {
*self = *self - rhs;
}
}
impl std::ops::Mul for ModInt {
type Output = ModInt;
fn mul(self, rhs: ModInt) -> Self::Output {
ModInt((self.0 as u64 * rhs.0 as u64 % MODu as u64) as usize)
}
}
impl std::ops::MulAssign for ModInt {
fn mul_assign(&mut self, rhs: ModInt) {
*self = *self * rhs;
}
}
impl std::ops::Neg for ModInt {
type Output = ModInt;
fn neg(self) -> Self::Output {
ModInt(if self.0 == 0 {0} else {MODu - self.0})
}
}
impl std::fmt::Display for ModInt {
fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
impl std::str::FromStr for ModInt {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let val = s.parse::<usize>()?;
Ok(ModInt::new(val))
}
}
impl PartialEq for ModInt {
fn eq(&self, other: &Self) -> bool {
self.0 == other.0
}
}
impl Hash for ModInt {
fn hash<H: Hasher>(&self, state: &mut H) {
self.0.hash(state);
self.0.hash(state);
}
}
impl Eq for ModInt {}
#[allow(dead_code)]
impl ModInt {
pub fn new(n: usize) -> ModInt {
ModInt(n % MODu)
}
pub fn zero() -> ModInt {
ModInt(0)
}
pub fn one() -> ModInt {
ModInt(1)
}
pub fn pow(self, mut n: usize) -> ModInt {
let mut t = ModInt::one();
let mut s = self;
while n > 0 {
if n & 1 == 1 {
t *= s;
}
s *= s;
n >>= 1;
}
t
}
pub fn inv(self) -> ModInt {
self.pow(MODu - 2)
}
}
// ---------- end ModInt ----------
/// Equivalent to std::lowerbound and std::upperbound in c++
pub trait BinarySearch<T> {
fn lower_bound(&self, x:&T) -> usize;
fn upper_bound(&self, x:&T) -> usize;
}
impl<T: Ord> BinarySearch<T> for VecDeque<T>{
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less => {
low = mid + 1;
}
Ordering::Equal | Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less | Ordering::Equal => {
low = mid + 1;
}
Ordering::Greater => {
high = mid;
}
}
}
low
}
}
impl<T: Ord> BinarySearch<T> for [T]{
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less => {
low = mid + 1;
}
Ordering::Equal | Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less | Ordering::Equal => {
low = mid + 1;
}
Ordering::Greater => {
high = mid;
}
}
}
low
}
}
fn matmul(A:&Vec<Vec<i64>>, B:&Vec<Vec<i64>>) -> Vec<Vec<i64>>{
let mut C = vec![vec![0;B[0].len()];A.len()];
for i in 0..A.len(){
for k in 0..B.len(){
for j in 0..B[0].len(){
C[i][j] += A[i][k]*B[k][j];
C[i][j] %= MOD;
}
}
}
return C;
}
fn matpow(A:&mut Vec<Vec<i64>>, n:usize) -> Vec<Vec<i64>>{
let mut B = vec![vec![0;A.len()];A.len()];
for i in 0..A.len(){
B[i][i] = 1;
}
let mut n = n;
let mut tmp = A.clone();
while(n>0){
if n&1 == 1{B = matmul(&B, &tmp);}
tmp = matmul(&tmp, &tmp);
n>>=1;
}
return B;
}
fn divisor(n:usize) -> Vec<usize>{
let mut res:Vec<usize> = Vec::new();
for i in 1..n+1{
if i*i>n{break;}
if n%i == 0{
res.push(i);
if i != n/i{
res.push(n/i);
}
}
}
res
}
struct UnionFind{
par:Vec<usize>,
rank:Vec<usize>,
size:Vec<usize>,
size_edge:Vec<usize>,
}
impl UnionFind{
fn init(n:usize) -> UnionFind{
let mut par = vec![0;n];
for i in 0..n{
par[i] = i;
}
UnionFind{
par:par,
rank:vec![0;n],
size:vec![1;n],
size_edge:vec![0;n],
}
}
fn find(&mut self, x:usize) ->usize{
if(self.par[x] == x){
x
}
else{
let p = self.par[x];
let res = self.find(p);
self.par[x] = res;
res
}
}
fn same(&mut self, a:usize, b:usize)->bool{
self.find(a) == self.find(b)
}
fn unite(&mut self, a:usize, b:usize){
let x = self.find(a);
let y = self.find(b);
if x != y{
if (self.rank[x] < self.rank[y]){
self.par[x] = y;
self.size[y] += self.size[x];
self.size_edge[y] += self.size_edge[x];
self.size_edge[y] += 1;
}
else{
self.par[y] = x;
self.size[x] += self.size[y];
self.size_edge[x] += self.size_edge[y];
self.size_edge[x] += 1;
if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;}
}
}
else{
self.size_edge[x] += 1;
}
}
fn check_size(&mut self, a:usize) -> usize{
let x = self.find(a);
let s = self.size[x];
s
}
}
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
.collect::<Vec<_>>();
std::str::from_utf8(&buf).unwrap()
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
struct LazySegTree<BiOp> {
n: usize,
val: Vec<i64>,
ma:Vec<i64>,
op: BiOp,
e: i64,
upe:i64,
inf:i64,
}
impl<BiOp> LazySegTree<BiOp>
where BiOp: Fn(i64, i64) -> i64{
pub fn new(n_: usize, op: BiOp, e: i64, upe:i64, inf:i64) -> Self {
let mut n = 1;
while n < n_ { n *= 2; } // n is a power of 2
LazySegTree {n: n, val: vec![e; 2 * n ], ma:vec![upe;2*n], op: op, e: e, upe:upe, inf:inf}
}
pub fn query(&self, x:usize, y:usize, l:usize, r:usize, k:usize) -> i64 {
if (r<=x || y<=l) {return self.inf;}
if (x<=l && r<=y) {return self.ma[k];}
let mut L = self.query(x,y,l,(l+r)/2, k*2);
let mut R = self.query(x,y,(l+r)/2,r, k*2+1);
return self.val[k] + (self.op)(L, R);
}
pub fn update(&mut self, x:usize, y:usize, v:i64, l:usize,r:usize, k:usize) {
if (l>=r) {return;}
if (x<=l && r<=y){
self.val[k]+=v;
self.ma[k]+=v;
}
else if(l<y && x<r){
self.update(x, y, v, l, (l+r)/2, k*2);
self.update(x,y,v,(l+r)/2,r, k*2+1);
self.ma[k] = self.val[k] + (self.op)(self.ma[k*2], self.ma[k*2+1]);
}
}
}
fn modinv(a:ModInt)->ModInt{
let mut a = a.0 as usize;
let mut b = MODu as i64;
let mut u = 1 as i64;
let mut v = 0 as i64;
let mut a = a as i64;
let mut m = MODu as i64;
while(b>0){
let mut t = a/b;
a -= t*b;
mem::swap(&mut a, &mut b);
u-=t*v;
mem::swap(&mut u, &mut v);
}
u%=m;
if u<0{u+=m;}
return ModInt(u as usize);
}
fn modpow(x:ModInt, n:ModInt) -> ModInt{
let mut ans = ModInt(1);
let mut n = n.0 as usize;
let mut x = x;
while(n != 0){
if (n&1 == 1){ans = ans*x;}
x = x*x;
n = n>>1;
}
ans
}
fn comb(a:usize, b:usize, fac:&Vec<ModInt>, ifac:&Vec<ModInt>)->ModInt{
let mut a = a;
let mut b = b;
if a == 0 && b == 0{return ModInt(1);}
if a<b || a<0{return ModInt(0);}
let mut tmp = ifac[a-b]*ifac[b];
return tmp * fac[a];
}
fn invs()->(Vec<ModInt>, Vec<ModInt>){
let mut fac = vec![ModInt(0);300001];
let mut ifac = vec![ModInt(0);300001];
fac[0] = ModInt(1);
ifac[0] = ModInt(1);
for i in 0..300000{
fac[i+1] = fac[i] * ModInt(i+1);
ifac[i+1] = ifac[i] * modpow(ModInt(i+1), ModInt(MODu - 2));
}
(fac, ifac)
}
struct ConvexHallTrick {
Q: Vec<(i64, i64)>,
}
impl ConvexHallTrick{
pub fn new() -> Self {
ConvexHallTrick {Q: Vec::new()}
}
pub fn calc(&self, p:(i64, i64), x:i64)->i64{
return p.0 * x + p.1;
}
pub fn dodo(& self, A:(i64, i64), B:(i64, i64), C:(i64, i64)) -> bool{
//max or min
(A.1 - C.1) * (B.0 - A.0) <= (A.1 - B.1)*(C.0 - A.0)
}
pub fn add(&mut self, a:i64, b:i64){
self.Q.push((a, b));
let mut v = self.Q.len();
while(v >=3 && self.dodo(self.Q[v-3], self.Q[v-2], self.Q[v-1])){
self.Q[v-2] = self.Q[v-1];
self.Q.pop();
v = self.Q.len();
}
}
pub fn query(& self, x:i64) -> i64{
let mut L = -1;
let mut R = (self.Q.len() - 1) as i64;
while(R-L>1){
let mut m = (L+R)/2;
if self.calc(self.Q[m as usize], x)>=self.calc(self.Q[m as usize+1], x){
L=m;
}
else{
R=m;
}
}
return self.calc(self.Q[R as usize], x);
}
}
#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);
impl<T: PartialOrd> PartialOrd for Rev<T> {
fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
other.0.partial_cmp(&self.0)
}
}
impl<T: Ord> Ord for Rev<T> {
fn cmp(&self, other: &Rev<T>) -> Ordering {
other.0.cmp(&self.0)
}
}
fn sieve(n:usize) -> (Vec<bool>, Vec<usize>){
let mut p:usize = 0;
let mut is_prime = vec![false; n+1];
let mut prime = Vec::new();
for i in 0..n+1{
is_prime[i] = true;
}
is_prime[0] = false;
is_prime[1] = false;
for i in 2..n+1{
if is_prime[i]{
prime.push(i as usize);
let mut j = 2*i;
while(j<=n){
is_prime[j] = false;
j+=i;
}
}
}
(is_prime, prime)
}
fn nHr(n:usize, r:usize, fac:&Vec<ModInt>, ifac:&Vec<ModInt>) -> ModInt{
comb(n + r - 1, r, fac, ifac)
}
fn gcd(a:usize, b:usize)->usize{
if b==0{return a;}
return gcd(b, a%b);
}
fn lcm(a:usize, b:usize)->usize{
return (b/gcd(a, b))*a;
}
struct SegTree_MOD<BiOp> {
n: usize,
dat: Vec<i64>,
op: BiOp,
e: i64,
mod_:i64,
}
impl<BiOp> SegTree_MOD<BiOp>
where BiOp: Fn(i64, i64) -> i64
{
pub fn new(n_: usize, op: BiOp, e: i64, mod_:i64) -> Self {
let mut n = 1;
while n < n_ { n *= 2; } // n is a power of 2
SegTree_MOD {n: n, dat: vec![e; 2 * n - 1], op: op, e: e, mod_:mod_}
}
/* ary[k] <- v */
pub fn update(&mut self, idx: usize, v: i64) {
let mut k = idx + self.n - 1;
self.dat[k] = v;
while k > 0 {
k = (k - 1) / 2;
self.dat[k] = (self.op)(self.dat[2 * k + 1], self.dat[2 * k + 2]);
self.dat[k] %= self.mod_;
}
}
/* [a, b) (note: half-inclusive)
* http://proc-cpuinfo.fixstars.com/2017/07/optimize-segment-tree/ */
pub fn query(&self, mut a: usize, mut b: usize) -> i64 {
let mut left = self.e;
let mut right = self.e;
a += self.n - 1;
b += self.n - 1;
while a < b {
if (a & 1) == 0 {
left = (self.op)(left, self.dat[a]);
left %= self.mod_;
}
if (b & 1) == 0 {
right = (self.op)(self.dat[b - 1], right);
right %= self.mod_;
}
a = a / 2;
b = (b - 1) / 2;
}
let mut res = (self.op)(left, right);
res %= self.mod_;
res
}
}
fn modpow2(x:usize, n:usize) -> usize{
let mut ans = 1;
let mut n = n;
let mut x = x;
while(n != 0){
if (n&1 == 1){ans = ans*x%MODu;}
x = x*x%MODu;
n = n>>1;
}
ans
}
#[derive(Clone)]
struct PPUnionFind{
par:Vec<usize>,
rank:Vec<usize>,
time:Vec<usize>,
now:usize,
history:Vec<(usize, usize)>,
}
impl PPUnionFind{
fn init(n:usize) -> PPUnionFind{
let mut par = vec![0;n];
for i in 0..n{
par[i] = i;
}
PPUnionFind{
par:par,
rank:vec![0;n],
time:vec![INF as usize;n],
now:0,
history:vec![],
}
}
fn find(&mut self, t:usize, x:usize) ->usize{
if self.time[x] > t{return x;}
else { let tt = self.par[x]; return self.find(t, tt);}
}
fn unite(&mut self, x:usize, y:usize) -> usize{
self.now+=1;
let mut x = x;
let mut y = y;
let nc = self.now;
x = self.find(nc, x);
y = self.find(nc, y);
if x == y{return self.now;}
if self.par[x] < self.par[y] {mem::swap(&mut x, &mut y);}
self.par[x] += self.par[y];
self.history.push((self.now, self.par[x]));
self.par[y] = x;
self.time[y] = self.now;
return self.now;
}
}
fn prim(cost:&Vec<Vec<(usize, i64)>>, vs:usize)->i64{
let mut used = vec![false; vs];
let mut bh = BinaryHeap::new();
for j in 0..cost[0].len(){
bh.push((cost[0][j].1, cost[0][j].0));
}
used[0] = true;
let mut res = 0;
while(bh.len()!=0){
let mut m = bh.pop().unwrap();
if used[m.1]{continue;}
used[m.1] = true;
for e in 0..cost[m.1].len(){
if used[cost[m.1][e].0] == false{
bh.push((cost[m.1][e].1, cost[m.1][e].0));
}
}
res += m.0;
}
return res;
}
fn kruscal(cost:&mut Vec<(i64, usize, usize)>, vs:usize)->i64{
cost.sort();
let mut uf = UnionFind::init(vs);
let mut res = 0;
for i in 0..cost.len(){
let e = cost[i].clone();
if uf.find(e.1) != uf.find(e.2){
uf.unite(e.1, e.2);
res += e.0;
}
}
return res;
}
fn kruscal3(cost:&mut Vec<(f64, usize, usize, usize)>, vs:usize)->(UnionFind, Vec<usize>) {
cost.sort_by(|a, b| (&a.0).partial_cmp(&b.0).unwrap());
let mut uf = UnionFind::init(vs);
let mut res = 0.0;
let mut rv = Vec::new();
let mut c = 0.0;
let mut t = 0.0;
for i in 0..cost.len(){
let e = cost[i].clone();
if uf.find(e.1) != uf.find(e.2){
uf.unite(e.1, e.2);
rv.push(e.3);
}
}
return (uf,rv);
}
fn kruscal2(cost:&mut Vec<(f64, usize, usize)>, vs:usize)->f64{
cost.sort_by(|a, b| (&a.0).partial_cmp(&b.0).unwrap());
let mut uf = UnionFind::init(vs);
let mut res = 0.0;
for i in 0..cost.len(){
let e = cost[i].clone();
if uf.find(e.1) != uf.find(e.2){
uf.unite(e.1, e.2);
res+= e.0;
}
}
return res;
}
struct segtree<I, Op>{
n: usize,
dat: Vec<I>,
op:Op,
e:I,
}
impl<I, Op> segtree<I, Op>
where Op: Fn(I, I) -> I, I:Copy{
pub fn new(n_:usize, op: Op, e:I)->Self{
let mut n = 1;
while(n<n_){n*=2;}
segtree{n: n, dat:vec![e; 2*n-1], op:op, e:e}
}
pub fn update(&mut self, k:usize, a:I){
let mut k = k;
k += self.n-1;
self.dat[k] = a;
while(k>0){
k = (k-1)/2;
self.dat[k] = (self.op)(self.dat[k*2 + 1], self.dat[k*2+2]);
}
}
pub fn query(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> I{
if r<=a || b<=l{return self.e;}
if a<=l && r<=b{return self.dat[k];}
else{
let mut vl = self.query(a, b, k*2+1, l, (l+r)/2);
let mut vr = self.query(a, b, k*2+2, (l+r)/2, r);
return (self.op)(vl, vr);
}
}
}
struct BIT{
n:usize,
bit:Vec<i64>,
e:i64,
ini:i64,
}
impl BIT{
/* 1-index*/
pub fn new(n_:usize, e:i64, ini:i64)->Self{
BIT{n:n_, bit:vec![e;n_+1], e:e, ini:ini}
}
pub fn sum(&self, i:usize)->i64{
let mut s = self.ini;
let mut i = i as i64;
while(i>0){
s = s+self.bit[i as usize];
i -= i & -i;
}
return s;
}
pub fn add(&mut self, i:usize, x:i64){
let mut i = i as i64;
while(i<=self.n as i64){
self.bit[i as usize] = self.bit[i as usize] + x;
i += i & -i;
}
}
}
struct Dsegtree{
n: usize,
datA: Vec<i64>,
datB:Vec<i64>,
e:i64,
}
impl Dsegtree{
pub fn new(n_:usize, e:i64)->Self{
Dsegtree{n:n_, datA:vec![e; 1<<22 - 1], datB:vec![e;1<<22 - 1], e:e}
}
pub fn update(&mut self,a:usize, b:usize, x:i64, k:usize, l:usize, r:usize){
//println!("{} {} {} {} {} {}", a, b, x, k , l, r);
if a<=l && r<=b{
self.datA[k] += x;
}
else if (l<b && a<r){
self.datB[k] += (cmp::min(b, r) as i64 - cmp::max(a, l) as i64) * x;
self.update(a, b, x, k*2+1, l, (l+r)/2);
self.update(a, b, x, k*2+2, (l+r)/2, r);
}
}
pub fn query(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> i64{
if (b<=l || r<=a){
return 0;
}
else if (a<=l && r<=b){
return self.datA[k] * ((r as i64-l as i64)) + self.datB[k];
}
else{
let mut res = (cmp::min(b, r) as i64 - cmp::max(a, l) as i64)* self.datA[k];
res += self.query(a, b, k*2+1, l, (l+r)/2);
res += self.query(a, b, k*2+2, (l+r)/2, r);
return res;
}
}
}
/*
unwrap_or_else
*/
fn prime_factor(n:usize)->HashMap<usize, usize>{
let mut res = HashMap::new();
let mut n = n;
for i in 2..n{
if i*i>n{break;}
while(n%i==0){
*res.entry(i).or_insert(0)+=1;
n/=i;
}
}
if n != 1{
res.insert(n, 1);
}
res
}
struct rollinghash{
base:Vec<i64>,
Mod:Vec<i64>,
hash:Vec<Vec<i64>>,
power:Vec<Vec<i64>>,
}
impl rollinghash{
pub fn new(s:&Vec<usize>)->Self{
let mut n = s.len();
let mut base = vec![1007, 2009];
let mut hash = vec![vec![0;n+1];2];
let mut power = vec![vec![1;n+1];2];
let mut Mod = vec![1000000007, 1000000009];
for iter in 0..2{
let mut ht = vec![0;n+1];
let mut pt = vec![1;n+1];
for i in 0..n{
hash[iter][i+1] = (hash[iter][i] * base[iter] + s[i] as i64) % Mod[iter];
power[iter][i+1] = power[iter][i] * base[iter] % Mod[iter];
}
}
return rollinghash{base:base, Mod:Mod, hash:hash, power:power}
}
pub fn get(&self, l:usize, r:usize)->(i64, i64){
let mut res = self.hash[0][r] - self.hash[0][l] * self.power[0][r-l] % self.Mod[0];
if res<0{
res += self.Mod[0];
}
let mut res2 = self.hash[1][r] - self.hash[1][l] * self.power[1][r-l] % self.Mod[1];
if res2<0{
res2 += self.Mod[1];
}
return (res, res2);
}
}
struct LCA{
G:Vec<Vec<i64>>,
parent:Vec<Vec<i64>>,
depth:Vec<i64>,
root:i64,
}
impl LCA{
pub fn new(G:Vec<Vec<i64>>, N:i64,R:i64)->Self{
let D = (f64::log2(N as f64)) as i64 + 2;
LCA{G:G, parent:vec![vec![0;N as usize];1+D as usize], depth:vec![0;N as usize], root:R}
}
pub fn getP(&mut self, v:i64, p:i64, d:i64){
self.parent[0][v as usize] = p;
self.depth[v as usize] = d;
for i in 0..self.G[v as usize].len(){
if self.G[v as usize][i as usize] != p{
let n = self.G[v as usize][i as usize];
self.getP(n, v, d+1);
}
}
}
pub fn init(&mut self){
let root = self.root;
self.getP(root, -1, 0);
let V = self.depth.len();
let logN = f64::log2(V as f64) as i64 + 2;
for k in 0..logN{
for v in 0..V{
if self.parent[k as usize][v as usize] <0{
self.parent[k as usize+1][v as usize] = -1;
}
else{
self.parent[k as usize+1][v as usize] = self.parent[k as usize][ (self.parent[k as usize][v as usize]) as usize];
}
}
}
}
fn ft(&self, f:i64, d:i64)->i64{
let mut now = f;
let mut now2 = 0;
let V = self.depth.len();
let logN = f64::log2(V as f64) as i64 + 2;
let mut v = f;
for k in 0..logN{
if (d >> k) & 1 == 1{
v = self.parent[k as usize][v as usize];
}
}
return v;
}
fn lca(&mut self,u:i64, v:i64)->i64{
let mut u = u;
let mut v = v;
if self.depth[u as usize] > self.depth[v as usize]{
mem::swap(&mut u, &mut v);
}
let mut V = self.depth.len();
let logN = f64::log2(V as f64) as i64 + 2;
for k in 0..logN{
if ((self.depth[v as usize] - self.depth[u as usize]) >> k)&1 == 1{
v = self.parent[k as usize][v as usize];
}
}
if u == v{return u;}
for k in (0..logN).rev(){
if self.parent[k as usize][u as usize] != self.parent[k as usize][v as usize]{
u = self.parent[k as usize][u as usize];
v = self.parent[k as usize][v as usize];
}
}
return self.parent[0][u as usize];
}
fn dist(&mut self,u:i64, v:i64)->i64{
let lc = self.lca(u, v);
return self.depth[u as usize] + self.depth[v as usize] - 2* self.depth[lc as usize];
}
}
fn fast_prime_factor_table(ma:usize)->Vec<usize>{
let mut p = sieve(1001);
let mut minf = vec![0;ma];
for j in 0..p.1.len(){
let P = p.1[j];
let mut now = P;
for i in 2..ma{
if minf[now] ==0{
minf[now] = P;
}
now+=P;
if now>=ma{
break;
}
}
}
return minf;
}
fn area_rectanble(x1:f64, x2:f64, x3:f64, y1:f64, y2:f64, y3:f64)->f64{
let tmp = x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1;
tmp.abs()/2.0
}
#[derive(PartialEq, Clone)]
struct FW(f64);
impl Eq for FW {}
impl PartialOrd for FW {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
self.0.partial_cmp(&other.0)
}
}
impl Ord for FW {
fn cmp(&self, other: &FW) -> Ordering {
other.partial_cmp(self).unwrap()
}
}
/* parsing
fn expr(s:&Vec<char>, i:&mut usize) -> Vec<usize>{
let mut val = term(s, i);
while(*i<s.len() && (s[*i] == '+' || s[*i] == '-')){
let mut op = encode(s[*i]);
*i+=1;
let mut val2 = term(s, i);
val = cal(val, val2, op);
}
return val;
}
fn term(s:&Vec<char>, i:&mut usize) -> Vec<usize>{
let mut val = factor(s, i);
while(*i<s.len() && s[*i] == '*'){
let mut op = encode(s[*i]);
*i+=1;
let mut val2 = factor(s, i);
val = cal(val, val2, op);
}
return val;
}
fn factor(s:&Vec<char>, i:&mut usize)->Vec<usize>{
if s[*i] == 'R' || s[*i] == 'S' || s[*i] == 'P' || s[*i] == '?'{
let mut res = encode(s[*i]);
*i+=1;
return res;
}
*i+=1;
let mut ret = expr(s, i);
*i+=1;
return ret;
}
*/
fn matmulf64(A:&Vec<Vec<f64>>, B:&Vec<Vec<f64>>) -> Vec<Vec<f64>>{
let mut C = vec![vec![0.0;B[0].len()];A.len()];
for i in 0..A.len(){
for k in 0..B.len(){
for j in 0..B[0].len(){
C[i][j] += A[i][k]*B[k][j];
}
}
}
return C;
}
//sort_by_key(|a| vec![a[0], -a[1]]);
//sort_by_key(|a| vec![a[0], -a[1]]);
////v.sort_by(|a, b| a.partial_cmp(b).unwrap());
struct UnionFind2 {
par: Vec<usize>,
rank: Vec<usize>,
}
impl UnionFind2 {
fn new(n: usize) -> UnionFind2 {
let mut vec = vec![0;n];
for i in 0..n {
vec[i] = i;
}
UnionFind2 {
par : vec,
rank : vec![0;n],
}
}
fn find(&mut self, x: usize) -> usize {
if x == self.par[x] {
x
}else{
let par = self.par[x];
let res = self.find(par);
self.par[x] = res;
res
}
}
fn same(&mut self, a: usize, b: usize) -> bool {
self.find(a) == self.find(b)
}
fn unite(&mut self, a: usize, b: usize){
let apar = self.find(a);
let bpar = self.find(b);
if self.rank[apar] > self.rank[bpar] {
self.par[bpar] = apar;
}else{
self.par[apar] = bpar;
if self.rank[apar] == self.rank[bpar] {
self.rank[bpar] += 1;
}
}
}
}
fn matmul2(A:&Vec<Vec<f64>>, B:&Vec<Vec<f64>>) -> Vec<Vec<f64>>{
let mut C = vec![vec![0.0;B[0].len()];A.len()];
for i in 0..A.len(){
for k in 0..B.len(){
for j in 0..B[0].len(){
C[i][j] += A[i][k]*B[k][j];
}
}
}
return C;
}
fn matpow2(A:&mut Vec<Vec<f64>>, n:usize) -> Vec<Vec<f64>>{
let mut B = vec![vec![0.0;A.len()];A.len()];
for i in 0..A.len(){
B[i][i] = 1.0;
}
let mut n = n;
let mut tmp = A.clone();
while(n>0){
if n&1 == 1{B = matmul2(&B, &tmp);}
tmp = matmul2(&tmp, &tmp);
n>>=1;
}
return B;
}
fn dijkstra(s:usize, g:&Vec<Vec<(usize, i64)>>)->Vec<i64>{
let mut dist = vec![INF;g.len()];
dist[s] = 0;
let mut h = BinaryHeap::new();
h.push((0, s));
while(h.len() != 0){
let mut t = h.pop().unwrap();
let mut d = t.0 * -1;
let mut v = t.1;
if dist[v]<d{
continue;
}
for i in 0..g[v].len(){
let n = g[v][i].0;
let dd = g[v][i].1;
if dist[n]>d+dd{
dist[n] = d+dd;
h.push((dist[n]*-1, n));
}
}
}
return dist;
}
fn base_number(n:usize, x:usize)->Vec<usize>{
if n == 0{
return vec![0];
}
let mut n = n;
let mut res = vec![];
let mut p = 0;
while(true){
if usize::pow(x, p)>n{
break;
}
p+=1;
}
for i in (0..p).rev(){
res.push(n/usize::pow(x, i));
n = n-(n/usize::pow(x, i))*usize::pow(x, i);
}
return res
}
#[macro_use]
fn solve(){
let sssss = std::io::stdin();
let mut sc = Scanner { stdin: sssss.lock() };
let mut N:usize = sc.read();
let mut V:usize = sc.read();
let mut L:usize = sc.read();
let mut x = vec![0i64;N];
let mut v = vec![0i64;N];
let mut w = vec![0i64;N];
for i in 0..N{
x[i] = sc.read();
v[i] = sc.read();
w[i] = sc.read();
}
x.push(L as i64);
v.push(0);
w.push(0);
x.insert(0, 0);
v.insert(0, 0);
w.insert(0, 0);
N+=2;
let mut h = BinaryHeap::new();
h.push((0, V as i64, 0));
let mut dp = vec![vec![INF;V+1];N+1];
dp[0][V] = 0;
while(h.len() != 0){
let mut t = h.pop().unwrap();
let mut co = t.0 as i64 * -1;
let mut tu = t.1;
let mut p = t.2;
if p == N-1{
continue;
}
if dp[p as usize][tu as usize]<co{
continue;
}
let dist = x[p as usize+1]-x[p as usize];
if dist<=tu{
let tmp = cmp::min(V as i64, (tu-dist+v[p as usize+1])) as usize;
if dp[p as usize+1][tmp]>co+w[p as usize+1]{
dp[p as usize+1][tmp]=co+w[p as usize+1];
h.push(((co + w[p as usize+1]) as i64 * -1, tmp as i64, p+1));
}
if dp[p as usize+1][(tu-dist) as usize]>co{
dp[p as usize+1][(tu-dist)as usize]=co;
h.push((co as i64 * -1 , tu-dist, p+1));
}
}
}
let mut res = INF;
for i in 0..V+1{
res = cmp::min(res, dp[N-1][i]);
}
if res == INF{
println!("{}", -1);
}
else{
println!("{}", res);
}
}
fn main(){
solve();
}
const PI:f64 = std::f64::consts::PI;
pub static MOD:i64 = 1000000007;
pub static MODu:usize = 1000000007;
pub static eps:f64 = 1e-6;
const INF: i64 = 1 << 62;