4 条题解

  • 1
    @ 2025-7-25 10:00:06

    我的头文件可能有亿点点长,呵呵。

    • 1
      @ 2025-7-25 9:59:13
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <algorithm>
      #include <bitset>
      #include <cctype>
      #include <cerrno>
      #include <clocale>
      #include <cmath>
      #include <complex>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <ctime>
      #include <deque>
      #include <exception>
      #include <fstream>
      #include <functional>
      #include <limits>
      #include <list>
      #include <map>
      #include <iomanip>
      #include <ios>
      #include <iosfwd>
      #include <iostream>
      #include <istream>
      #include <ostream>
      #include <queue>
      #include <set>
      #include <sstream>
      #include <stack>
      #include <stdexcept>
      #include <streambuf>
      #include <string>
      #include <utility>
      #include <vector>
      #include <cwchar>
      #include <cwctype>
      #include <complex.h>
      #include <fenv.h>
      #include <inttypes.h>
      #include <stdbool.h>
      #include <stdint.h>
      #include <tgmath.h>
      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      using namespace std;
      const int N=1e6+10;
      const int INF=0x3f3f3f3f;
      int n,m,w[N],c[N],x,y,z,dp[N];
      int len;
      int main()
      {
      	cin>>n>>m;
      	for(int i=1;i<=n;i++){
      		cin>>x>>y>>z;
      		if(!z) z=m/x;
      		if(z==-1) z=1;
      		int sb=1;
      		while(sb<=z){
      			w[++len]=sb*x;
      			c[len]=sb*y;
      			z-=sb;
      			sb*=2;
      		}
      		if(z){
      			w[++len]=z*x;
      			c[len]=z*y;
      		}
      	}
      	for(int i=1;i<=len;i++)
      		for(int j=m;j>=w[i];j--)
      			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
      	cout<<dp[m];
      	return 0;
      }
      
      
      
      
      • 1
        @ 2025-7-25 9:59:09
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        #include <algorithm>
        #include <bitset>
        #include <cctype>
        #include <cerrno>
        #include <clocale>
        #include <cmath>
        #include <complex>
        #include <cstdio>
        #include <cstdlib>
        #include <cstring>
        #include <ctime>
        #include <deque>
        #include <exception>
        #include <fstream>
        #include <functional>
        #include <limits>
        #include <list>
        #include <map>
        #include <iomanip>
        #include <ios>
        #include <iosfwd>
        #include <iostream>
        #include <istream>
        #include <ostream>
        #include <queue>
        #include <set>
        #include <sstream>
        #include <stack>
        #include <stdexcept>
        #include <streambuf>
        #include <string>
        #include <utility>
        #include <vector>
        #include <cwchar>
        #include <cwctype>
        #include <complex.h>
        #include <fenv.h>
        #include <inttypes.h>
        #include <stdbool.h>
        #include <stdint.h>
        #include <tgmath.h>
        #include <stdio.h>
        #include <string.h>
        #include <math.h>
        using namespace std;
        const int N=1e6+10;
        const int INF=0x3f3f3f3f;
        int n,m,w[N],c[N],x,y,z,dp[N];
        int len;
        int main()
        {
        	cin>>n>>m;
        	for(int i=1;i<=n;i++){
        		cin>>x>>y>>z;
        		if(!z) z=m/x;
        		if(z==-1) z=1;
        		int sb=1;
        		while(sb<=z){
        			w[++len]=sb*x;
        			c[len]=sb*y;
        			z-=sb;
        			sb*=2;
        		}
        		if(z){
        			w[++len]=z*x;
        			c[len]=z*y;
        		}
        	}
        	for(int i=1;i<=len;i++)
        		for(int j=m;j>=w[i];j--)
        			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        	cout<<dp[m];
        	return 0;
        }
        
        
        
        
        • 0
          @ 2025-7-25 9:59:22
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          #include <algorithm>
          #include <bitset>
          #include <cctype>
          #include <cerrno>
          #include <clocale>
          #include <cmath>
          #include <complex>
          #include <cstdio>
          #include <cstdlib>
          #include <cstring>
          #include <ctime>
          #include <deque>
          #include <exception>
          #include <fstream>
          #include <functional>
          #include <limits>
          #include <list>
          #include <map>
          #include <iomanip>
          #include <ios>
          #include <iosfwd>
          #include <iostream>
          #include <istream>
          #include <ostream>
          #include <queue>
          #include <set>
          #include <sstream>
          #include <stack>
          #include <stdexcept>
          #include <streambuf>
          #include <string>
          #include <utility>
          #include <vector>
          #include <cwchar>
          #include <cwctype>
          #include <complex.h>
          #include <fenv.h>
          #include <inttypes.h>
          #include <stdbool.h>
          #include <stdint.h>
          #include <tgmath.h>
          #include <stdio.h>
          #include <string.h>
          #include <math.h>
          using namespace std;
          const int N=1e6+10;
          const int INF=0x3f3f3f3f;
          int n,m,w[N],c[N],x,y,z,dp[N];
          int len;
          int main()
          {
          	cin>>n>>m;
          	for(int i=1;i<=n;i++){
          		cin>>x>>y>>z;
          		if(!z) z=m/x;
          		if(z==-1) z=1;
          		int sb=1;
          		while(sb<=z){
          			w[++len]=sb*x;
          			c[len]=sb*y;
          			z-=sb;
          			sb*=2;
          		}
          		if(z){
          			w[++len]=z*x;
          			c[len]=z*y;
          		}
          	}
          	for(int i=1;i<=len;i++)
          		for(int j=m;j>=w[i];j--)
          			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
          	cout<<dp[m];
          	return 0;
          }
          
          
          
          
          • 1

          信息

          ID
          3275
          时间
          1000ms
          内存
          256MiB
          难度
          5
          标签
          递交数
          144
          已通过
          58
          上传者