{-# LANGUAGE MultiWayIf #-}

module Main where

import           Control.Monad
import           Control.Monad.Extra
import qualified Data.Array as A
import qualified Data.Array.IO as AIO
import qualified Data.Array.Unboxed as AU
import           Data.Bits
import           Data.Bool
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BSC8
import           Data.Char
import           Data.Either
import           Data.Function
import qualified Data.Graph.Inductive.Graph as G
import qualified Data.Graph.Inductive.PatriciaTree as G
import qualified Data.Heap as H
import           Data.Int
import           Data.List
import qualified Data.Map.Strict as M
import           Data.Maybe
import           Data.Monoid
import           Data.Ord
import qualified Data.Sequence as SQ
import qualified Data.Set as S
import           Data.Tuple
import qualified Data.Vector as V
import           Data.Vector.Algorithms.Search
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import           Debug.Trace

m = 10 ^ 6

main = do
  --aN       <- getI
  --[aA, aB] <- getIL
  --aS       <- getLine
  [aN, aK] <- getIL
  aP <- getVUI
  aC <- getVUI
  dTable <- VM.replicateM 60 $ VUM.replicate aN (0, 0, 0)
    :: IO (VM.IOVector (VUM.IOVector (Int, Int, Int)))
  VU.imapM_
    (\i x -> do
       ddTable <- VM.read dTable 0
       VUM.write ddTable i (aP VU.! i - 1, aC VU.! i, aC VU.! i))
    aP
  VU.mapM_
    (\d -> VU.mapM_
       (\v -> do
          dsuccTable <- VM.read dTable (d + 1)
          ddTable <- VM.read dTable d
          (dvnext, dvval, dvall) <- VUM.read ddTable v
          (ddvnext, ddvval, ddvall) <- VUM.read ddTable dvnext
          VUM.write
            dsuccTable
            v
            (ddvnext, dvval + ddvval, max dvall $ dvval + ddvall))
     $ VU.enumFromN 0 aN)
    $ VU.enumFromN 0 59
  ans1 <- VU.foldM
    (\acc1 x -> do
       (ans2, _, _) <- VU.foldM
         (\acc2@(ans3, sum, offset) d -> do
            if (aK .&. (shiftL 1 d) /= 0)
              then do
                ddTable <- VM.read dTable d
                (donext, doval, doall) <- VUM.read ddTable offset
                return (max ans3 $ sum + doall, sum + doval, donext)
              else return acc2)
         (acc1, 0, x)
         (VU.enumFromStepN 59 (-1) 60)
       return ans2)
    ((-10 ^ 9) * 5000 - 1)
    $ VU.enumFromN 0 aN
  print ans1
  --mapM_ (\x -> VM.read dTable x >>= VU.freeze >>= print) [0 .. 59]
  return ()

--雑多系
t :: Int -> (Int, Int)
t x = (x, 1)

i def f t = bool t def $ f t

myVUmap f vu =
  if vu == VU.empty
  then VU.empty
  else VU.unfoldr
    (\x -> let ret = f $ VU.head vu
           in if vu == VU.empty
              then Nothing
              else if isLeft ret
                   then Just (either id id ret, VU.tail vu)
                   else Just (either id id ret, VU.empty))
    vu

myVUmapM f vu =
  if vu == VU.empty
  then return VU.empty
  else VU.unfoldrM
    (\x -> do
       ret <- f $ VU.head vu
       if vu == VU.empty
         then return $ Nothing
         else if isLeft ret
              then return $ Just (either id id ret, VU.tail vu)
              else return $ Just (either id id ret, VU.empty))
    vu

myVUmapM_ f vu =
  if vu == VU.empty
  then return ()
  else do
    ret <- VU.unfoldrM
      (\x -> do
         ret <- f $ VU.head vu
         if vu == VU.empty
           then return $ Nothing
           else if isLeft ret
                then return $ Just (either id id ret, VU.tail vu)
                else return $ Just (either id id ret, VU.empty))
      vu
    return ()

myVUfor vu f = myVUmap f vu

myVUforM vu f = myVUmapM f vu

myVUforM_ vu f = myVUmapM_ f vu

myVUfoldl f acc vu =
  if vu == VU.empty
  then return acc
  else do
    let ret = f acc (VU.head vu)
    if isLeft ret
      then myVUfoldl f (either id id ret) (VU.tail vu)
      else return $ either id id ret

myVUfoldr f acc vu =
  if vu == VU.empty
  then return acc
  else do
    let ret = f acc (VU.last vu)
    if isLeft ret
      then myVUfoldr f (either id id ret) (VU.init vu)
      else return $ either id id ret

myVUfoldM f acc vu =
  if vu == VU.empty
  then return acc
  else do
    ret <- f acc (VU.head vu)
    if isLeft ret
      then myVUfoldM f (either id id ret) (VU.tail vu)
      else return $ either id id ret

--周りのマス
aroundSquare y x h w =
  [aYX
  | aYX@(aY, aX)
      <- [(y + a, x + b) | a <- [-1 .. 1], b <- [-1 .. 1], abs a + abs b == 1]
  , aY >= 1
  , aY <= h
  , aX >= 1
  , aX <= w]

--入力系
splitReadBSC8 :: BSC8.ByteString -> [Int]
splitReadBSC8 bs = let (bs1, newBs) = BSC8.splitAt 1 bs
                   in if newBs == BSC8.empty
                      then [test $ BSC8.readInt bs1]
                      else test (BSC8.readInt bs1):splitReadBSC8 newBs
  where
    test (Just (i, _)) = i

read2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> IO Char
read2DimChar vec y x = do
  vecY <- VM.read vec y
  VUM.read vecY x

write2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> Char -> IO ()
write2DimChar vec y x t = do
  vecY <- VM.read vec y
  VUM.write vecY x t

readTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> IO Int
readTwoDimVec vec y x = do
  vecY <- VM.read vec y
  VUM.read vecY x

writeTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> Int -> IO ()
writeTwoDimVec vec y x t = do
  vecY <- VM.read vec y
  VUM.write vecY x t

getVUI :: IO (VU.Vector Int)
getVUI = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine

getRepVUI :: Int -> IO (VU.Vector Int)
getRepVUI n = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) . BSC8.unlines
  <$> replicateM n BSC8.getLine

getVS :: IO (V.Vector Char)
getVS = V.fromList <$> getLine

getVUC :: IO (VU.Vector Char)
getVUC = VU.fromList <$> getLine

readI :: BSC8.ByteString -> Int
readI = fst . fromJust . BSC8.readInt

readIL :: BSC8.ByteString -> [Int]
readIL = map readI . BSC8.words

readIT2 :: BSC8.ByteString -> (Int, Int)
readIT2 bs = let words = BSC8.words bs
             in (readI $ head words, readI $ last words)

getI :: IO Int
getI = readI <$> BSC8.getLine

getIL :: IO [Int]
getIL = readIL <$> BSC8.getLine

getIT2 :: IO (Int, Int)
getIT2 = readIT2 <$> BSC8.getLine

getIT2Order :: IO (Int, Int)
getIT2Order = getIL
  >>= \x@[xz, xo] -> if xz > xo
                     then return (xo, xz)
                     else return (xz, xo)

getNIS :: Int -> IO [(Int, BSC8.ByteString)]
getNIS 0 = return []
getNIS n = do
  [aFst, aSnd] <- BSC8.words <$> BSC8.getLine
  next <- getNIS (n - 1)
  return ((readI aFst, aSnd):next)

il2Words :: [Int] -> String
il2Words = unwords . map show

il2Lines :: [Int] -> String
il2Lines = unlines . map show

--modNum = 10 ^ 9 + 7
--modulus = 1000000007
modulus = 1000000007

newtype MInt = M Int

instance Num MInt where
  (M a) + (M b) = M $ mod (a + b) modulus

  (M a) - (M b) = M $ mod (a - b) modulus

  (M a) * (M b) = M $ mod (a * b) modulus

  fromInteger a = M $ mod (fromInteger a) modulus

  abs (M a) = undefined

  signum (M a) = undefined

instance Show MInt where
  show (M a) = show (mod a modulus)

int2MInt :: Int -> MInt
int2MInt a = M (mod a modulus)

mInt2Int :: MInt -> Int
mInt2Int (M a) = a

{-
factsMod :: V.Vector MInt
factsMod = V.scanl (\acc x -> M x * acc) 1 $ V.generate 2000000 (+ 1)

factMod :: Int -> MInt
factMod = (factsMod V.!)
-}
factMod :: Int -> MInt
factMod n
  | n == 0 = 1
  | n == 1 = 1
  | otherwise = M n * factMod (n - 1)

factDivMod :: Int -> Int -> MInt
factDivMod n k
  | n == k = M 1
  | otherwise = M n * factDivMod (n - 1) k

powMod :: MInt -> MInt -> MInt
powMod n mK@(M k)
  | k == 0 = M 1
  | k == 1 = n
  | mod k 2 == 0 = powMod (n ^ 2) (M (div k 2))
  | otherwise = n * powMod (n ^ 2) (M (div k 2))

invMod :: MInt -> MInt
invMod (M 0) = error "inverse of 0"
invMod x = powMod x (M (modulus - 2))

{-
combiMod :: Int -> Int -> MInt
combiMod n k
  | n < 0 || k < 0 || k > n = 0
  | otherwise = factMod n * invMod (factMod (n - k)) * invMod (factMod k)
-}
combiMod :: Int -> Int -> MInt
combiMod n k
  | n < 0 || k < 0 || k > n = 0
  | k > n - k = factDivMod n k * invMod (factMod (n - k))
  | otherwise = factDivMod n (n - k) * invMod (factMod k)

combi :: Int -> Int -> Int
combi n k
  | n < 0 || k < 0 || k > n = 0
  | k == n = 1
  | otherwise = div (div (fact n) (fact (n - k))) (fact k)

{-w
primes :: Integral a => [a]
primes = map fromIntegral $ [2, 3] ++ primes'
 where
  primes' = [5] ++ f 1 7 primes'
  f m s (p : ps) = [ n | n <- ns, gcd m n == 1 ] ++ f (m * p) (p * p) ps
    where ns = [ x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4] ]

prime n = primes !! n
primes = sieve [2 ..]
sieve (p : xs) = p : sieve [ x | x <- xs, x `mod` p /= 0 ]
-}
fact :: Int -> Int
fact 0 = 1
fact n
  | n > 0 = n * fact (n - 1)

knappsackWDP :: Int -> [(Int, Int)] -> VU.Vector Int
knappsackWDP maxW [] = VU.replicate (maxW + 1) 0
knappsackWDP maxW ((w, v):xs) =
  let tailDP = knappsackWDP maxW xs
  in VU.generate (maxW + 1)
     $ \i -> if w <= i
             then max (tailDP VU.! i) (tailDP VU.! (i - w) + v)
             else tailDP VU.! i

knappsackVDP :: Int -> Int -> Int -> [(Int, Int)] -> VU.Vector Int
knappsackVDP maxW maxV n [] = VU.cons 0 $ VU.replicate (n * maxV) maxW
knappsackVDP maxW maxV n ((w, v):xs) =
  let tailDP = knappsackVDP maxW maxV n xs
  in VU.generate (n * maxV + 1)
     $ \i -> if v <= i
             then min (tailDP VU.! i) (tailDP VU.! (i - v) + w)
             else tailDP VU.! i

knappsackMinVol :: AIO.IOArray (Int, Int) Int
                -> VU.Vector Int
                -> VU.Vector Int
                -> Int
                -> Int
                -> IO Int
knappsackMinVol dp volumeVec valueVec dpSize maxVolume = do
  mapM_
    (\i -> mapM_
       (\v -> do
          let volume = volumeVec VU.! i
              value = valueVec VU.! i
          newdp <- if (v + value) > dpSize
                   then AIO.readArray dp (i, v)
                   else do
                     dpIVm <- AIO.readArray dp (i, v + value)
                     dpIV <- AIO.readArray dp (i, v)
                     return (min (dpIVm - volume) dpIV)
          AIO.writeArray dp (i + 1, v) newdp)
       (reverse [0 .. dpSize]))
    [0 .. VU.length valueVec - 1]
  foldM
    (\acc x -> do
       num <- AIO.readArray dp (VU.length volumeVec, x)
       return
         $ if num <= maxVolume
           then x
           else acc)
    0
    [0 .. dpSize]

lcsTable :: BS.ByteString -> BS.ByteString -> V.Vector (VU.Vector Int)
lcsTable xs ys = V.scanl step (VU.replicate (m + 1) 0) xs'
  where
    n = BS.length xs

    m = BS.length ys

    xs' = V.generate n $ BSC8.index xs :: V.Vector Char

    ys' = VU.generate m $ BSC8.index ys :: VU.Vector Char

    step :: VU.Vector Int -> Char -> VU.Vector Int
    step v x = VU.scanl innerStep 0 (VU.zip3 v (VU.tail v) ys')
      where
        innerStep :: Int -> (Int, Int, Char) -> Int
        innerStep a (b, c, y)
          | x == y = 1 + b
          | otherwise = max a c

{-
main = do
xs <- BS.getLine
ys <- BS.getLine
print $ VU.last $ V.last $ lcsTable xs ys
-}
myFilter :: (a -> Bool) -> [a] -> ([a], [a])
myFilter _pred [] = ([], [])
myFilter pred (x:xs)
  | pred x = let (l, r) = myFilter pred xs
             in (x:l, r)
  | otherwise = let (l, r) = myFilter pred xs
                in (l, x:r)

--UnionFindデータ構造
type UF_PARENT = VUM.IOVector Int

type UF_RANK = VUM.IOVector Int

type UF = (UF_PARENT, UF_RANK)

ufMakeSet :: Int -> IO UF
ufMakeSet n = do
  parent <- VU.thaw $ VU.generate n id
  rank <- VUM.replicate n 0
  return (parent, rank)

ufUnion :: UF -> Int -> Int -> IO ()
ufUnion unionFind@(parents, ranks) x y = do
  xRoot <- ufFind unionFind x
  yRoot <- ufFind unionFind y
  xRootRank <- VUM.read ranks xRoot
  yRootRank <- VUM.read ranks yRoot
  if
    | xRootRank > yRootRank -> VUM.write parents yRoot xRoot
    | xRootRank < yRootRank -> VUM.write parents xRoot yRoot
    | xRoot /= yRoot -> do
      VUM.write parents yRoot xRoot
      VUM.write ranks xRoot (xRootRank + 1)
    | otherwise -> return ()

ufFind :: UF -> Int -> IO Int
ufFind unionFind@(parents, ranks) x = do
  xParent <- VUM.read parents x
  if xParent == x
    then return x
    else do
      xRootParent <- ufFind unionFind xParent
      VUM.write parents x xRootParent
      return xRootParent

--UnDirectedGraph(無向グラフ)データ構造
type UDG = M.Map Int [Int]

list2UDG :: [(Int, Int)] -> M.Map Int [Int]
list2UDG = foldl
  (\acc x -> let lr = M.insertWith (++) (fst x) [snd x] acc
             in M.insertWith (++) (snd x) [fst x] lr)
  M.empty

--OSA-K法テーブル準備(お酒？)
osaKMethod m = do
  table <- VUM.replicate (m + 1) (0 :: Int) :: IO (VUM.IOVector Int)
  modi table m 2 1 1 (div m 2)
  loopModi table m 3
  VU.freeze table
  where
    loopModi table m x
      | x > m = return ()
      | otherwise = do
        modi table m x 1 2 (div m x)
        loopModi table m (x + 2)

    modi table m x n s nm
      | n > nm = return ()
      | otherwise = do
        let xn = x * n
        target <- VUM.read table xn
        if target == 0
          then do
            VUM.write table xn x
            modi table m x (n + s) s nm
          else if n == 1
               then return ()
               else modi table m x (n + s) s nm

getPrimes osaKTable target = VU.unfoldr
  (\x -> let minPrime = osaKTable VU.! target
             (prime, quo) = if minPrime == 0
                            then (target, 1)
                            else (target, div target minPrime)
         in if x == 1
            then Nothing
            else Just (prime, quo))
  target

--BinarySearchっぽいもの 1からmまでのすべての数値をFにいれたとき最初にTrueになる数値を見つける。
binarySearchFirstTrueSerialASC f m =
  binarySearchFirstTrueSerialASCP f 0 (m + 1)

binarySearchFirstTrueSerialASCP f l r =
  let i = l + (div (r - l) 2)
      test = f i
  in if
       | test && i - l == 1 -> i
       | test && i - l /= 1 -> binarySearchFirstTrueSerialASCP f l i
       | not test && r - i == 1 -> r
       | otherwise -> binarySearchFirstTrueSerialASCP f i r

--BinarySearchっぽいもの その２ vuiのすべての数値をFにいれたとき最初にTrueになる数値を見つける。
binarySearchFirstTrueList f vui = let lenl = VU.length vui
                                  in binarySearchFirstTrueListP f vui (-1) lenl

binarySearchFirstTrueListP f vui l r =
  let i = l + (div (r - l) 2)
      test = f (vui VU.! i)
  in if
       | test && i - l == 1 -> i
       | test && i - l /= 1 -> binarySearchFirstTrueListP f vui l i
       | not test && r - i == 1 -> r
       | otherwise -> binarySearchFirstTrueListP f vui i r

--MaxHeap関連
hMaxPoint :: Int
hMaxPoint = 101

hMaximum :: H.Heap Int -> Int
hMaximum h = hMaxPoint - (H.minimum h)

hInsertMax :: Int -> H.Heap Int -> H.Heap Int
hInsertMax x = H.insert (hMaxPoint - x)

hDeleteMax :: H.Heap Int -> H.Heap Int
hDeleteMax = H.deleteMin




Measured memory_bytes: 19176