Exact Word Segmentation

You are given a string text, an integer n, and a list of valid words dictionary. Your task is to determine whether the string can be segmented into exactly n words, such that each segmented word is present in the dictionary.

Formally, let \(S\) be the given string. You need to decide if there exists a segmentation of \(S = w_1w_2\cdots w_n\) where each \(w_i\) (for \(1 \leq i \leq n\)) is in the dictionary. Output YES if such a segmentation exists, and NO otherwise.

inputFormat

The input consists of three lines:

• The first line contains the string text.
• The second line contains an integer n, representing the required number of words.
• The third line contains the dictionary words separated by spaces.

outputFormat

Output a single line containing YES if the string can be segmented into exactly n words found in the dictionary, otherwise output NO.

thisisaword
4
this is a word

YES