#![allow(unused_imports)] #![cfg_attr(feature = "cargo-clippy", allow(redundant_field_names))] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; use std::io::{self, BufWriter, Read, Write}; use std::ops::{Add, Div, Mul, Sub}; use std::str::{self, FromStr}; use std::{cmp, fmt}; fn main() { let (n, c, ss, ts, ys, ms): (usize, u32, Vec, Vec, Vec, Vec) = { let mut sc = InputScanOnce::new(io::stdin(), 1024); let (n, c, v) = (sc.next(), sc.next(), sc.next()); (n, c, sc.vec(v), sc.vec(v), sc.vec(v), sc.vec(v)) }; let g = { let mut g = vec![vec![]; n]; for (((s, t), y), m) in ss.into_iter().zip(ts).zip(ys).zip(ms) { g[s - 1].push(E { t: t - 1, y, m }); } g }; let mut sts = vec![St { s: 0, y: 0, m: 0 }]; let mut r = None; while !sts.is_empty() { let mut sts_ = vec![]; for st in sts { for e in &g[st.s] { let st = St { s: e.t, y: st.y + e.y, m: st.m + e.m, }; if st.y <= c { if st.s == n - 1 { r = Some(match r { None => st.m, Some(r) => cmp::min(r, st.m), }); } else { sts_.push(st); } } } } sts = sts_; } match r { None => println!("-1"), Some(r) => println!("{}", r), } } #[derive(Clone, Copy, Debug)] struct E { t: usize, y: u32, m: u32, } struct St { s: usize, y: u32, m: u32, } struct InputScanOnce { buf: Vec, pos: usize, } #[allow(dead_code)] impl InputScanOnce { fn new(mut reader: R, estimated: usize) -> Self { let mut buf = Vec::with_capacity(estimated); let _ = io::copy(&mut reader, &mut buf).unwrap(); InputScanOnce { buf: buf, pos: 0 } } #[inline] fn next(&mut self) -> T where T::Err: fmt::Debug, { let mut start = None; loop { match (self.buf[self.pos], start.is_some()) { (b' ', true) | (b'\n', true) => break, (_, true) | (b' ', false) | (b'\n', false) => self.pos += 1, (_, false) => start = Some(self.pos), } } let target = &self.buf[start.unwrap()..self.pos]; unsafe { str::from_utf8_unchecked(target) }.parse().unwrap() } fn vec(&mut self, n: usize) -> Vec where T::Err: fmt::Debug, { (0..n).map(|_| self.next()).collect() } fn pairs(&mut self, n: usize) -> Vec<(T1, T2)> where T1::Err: fmt::Debug, T2::Err: fmt::Debug, { (0..n).map(|_| (self.next(), self.next())).collect() } fn trios(&mut self, n: usize) -> Vec<(T1, T2, T3)> where T1::Err: fmt::Debug, T2::Err: fmt::Debug, T3::Err: fmt::Debug, { (0..n) .map(|_| (self.next(), self.next(), self.next())) .collect() } fn mat(&mut self, m: usize, n: usize) -> Vec> where T::Err: fmt::Debug, { (0..m).map(|_| self.vec(n)).collect() } fn strings_as_mat T>(&mut self, h: usize, mut f: F) -> Vec> { (0..h) .map(|_| { let l = self.next::(); l.as_bytes().iter().cloned().map(&mut f).collect() }) .collect() } }