Speed Dial
Contest: Educational Codeforces Round 55 (Rated for Div. 2)
Difficulty rating: 2800
Tags: dp, strings, trees

Polycarp's phone book contains $$$n$$$ phone numbers, each of them is described by $$$s_i$$$ — the number itself and $$$m_i$$$ — the number of times Polycarp dials it in daily.

Polycarp has just bought a brand new phone with an amazing speed dial feature! More precisely, $$$k$$$ buttons on it can have a number assigned to it (not necessary from the phone book). To enter some number Polycarp can press one of these $$$k$$$ buttons and then finish the number using usual digit buttons (entering a number with only digit buttons is also possible).

Speed dial button can only be used when no digits are entered. No button can have its number reassigned.

What is the minimal total number of digit number presses Polycarp can achieve after he assigns numbers to speed dial buttons and enters each of the numbers from his phone book the given number of times in an optimal way?

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 500$$$, $$$1 \le k \le 10$$$) — the amount of numbers in Polycarp's phone book and the number of speed dial buttons his new phone has.

The $$$i$$$-th of the next $$$n$$$ lines contain a string $$$s_i$$$ and an integer $$$m_i$$$ $$$(1 \le m_i \le 500)$$$, where $$$s_i$$$ is a non-empty string of digits from $$$0$$$ to $$$9$$$ inclusive (the $$$i$$$-th number), and $$$m_i$$$ is the amount of times it will be dialed, respectively.

It is guaranteed that the total length of all phone numbers will not exceed $$$500$$$.

Output format:
Print a single integer — the minimal total number of digit number presses Polycarp can achieve after he assigns numbers to speed dial buttons and enters each of the numbers from his phone book the given number of times in an optimal way.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The only speed dial button in the first example should have "0001" on it. The total number of digit button presses will be $$$0 \cdot 5$$$ for the first number + $$$3 \cdot 4$$$ for the second + $$$2 \cdot 1$$$ for the third. $$$14$$$ in total.

The only speed dial button in the second example should have "00" on it. The total number of digit button presses will be $$$2 \cdot 5$$$ for the first number + $$$1 \cdot 6$$$ for the second + $$$2 \cdot 1$$$ for the third. $$$18$$$ in total.

Example input:
3 1
0001 5
001 4
01 1

Example output:
14

Example input:
3 1
0001 5
001 6
01 1

Example output:
18

Editorial:
The first thing to come to one's mind is dynamic programming on a trie. The most naive of the solutions take $$$O(S \cdot n^2 \cdot k^2)$$$, where $$$S$$$ is the total length of strings.
I'll introduce the faster approach.
Let $$$dp[x][rem][k]$$$ be the solution for subtree of the vertex $$$x$$$ with $$$rem$$$ buttons remaining and $$$k$$$ is the closest ancestor vertex with the button used in it.
This dp will be recalced via the other dp.
Let $$$dp2[x][rem][k][m]$$$ be the same thing as $$$dp[x][rem][k]$$$ but only $$$m$$$ first children of $$$x$$$ is taken into consideration and $$$x$$$ doesn't have a button in it.
Give $$$z$$$ buttons to the current child, then update $$$dp2[x][rem][k][m]$$$ with $$$dp[m-th child of x][z][k][m]$$$ + $$$dp2[x][rem - z][k][m + 1]$$$.
$$$dp[x][rem][k]$$$ will then have two options: $$$dp[x][rem - 1][x]$$$ for $$$x$$$ having button in it and $$$dp2[x][rem][k][0]$$$ for $$$x$$$ not having button in it.
$$$dp[x][rem][k]$$$ has $$$O(1)$$$ transitions and $$$O(len^2 \cdot p)$$$ states.
$$$dp2[x][rem][k][m]$$$ has $$$O(k)$$$ total transitions and also $$$O(len^2 \cdot p)$$$ states.