


"""simple docstring"""



import json
from typing import Iterator, List, Union

from tokenizers import AddedToken, Regex, Tokenizer, decoders, normalizers, pre_tokenizers, trainers
from tokenizers.implementations.base_tokenizer import BaseTokenizer
from tokenizers.models import Unigram
from tokenizers.processors import TemplateProcessing







class    __a						( __snake_case							):







				def __init__( self      ,	UpperCAmelCase = "▁"      ,	UpperCAmelCase = True      ,	UpperCAmelCase = "<unk>"      ,	UpperCAmelCase = "</s>"      ,	UpperCAmelCase = "<pad>"      ,	):

					'''simple docstring'''






					lowerCAmelCase_      							=			{
					    '''pad''': {'''id''': 0, '''token''': pad_token},
					    '''eos''': {'''id''': 1, '''token''': eos_token},
					    '''unk''': {'''id''': 2, '''token''': unk_token},
					}

					lowerCAmelCase_      							=			[None] * len(self.special_tokens   )
					for token_dict in self.special_tokens.values():
						lowerCAmelCase_      							=			token_dict['''token''']

					lowerCAmelCase_      							=			Tokenizer(Unigram()   )

					lowerCAmelCase_      							=			normalizers.Sequence(
					    [
					        normalizers.Nmt(),
					        normalizers.NFKC(),
					        normalizers.Replace(Regex(''' {2,}'''   )      ,	''' '''   ),
					        normalizers.Lowercase(),
					    ]   )
					lowerCAmelCase_      							=			pre_tokenizers.Sequence(
					    [
					        pre_tokenizers.Metaspace(replacement=UpperCAmelCase      ,	add_prefix_space=UpperCAmelCase   ),
					        pre_tokenizers.Digits(individual_digits=UpperCAmelCase   ),
					        pre_tokenizers.Punctuation(),
					    ]   )
					lowerCAmelCase_      							=			decoders.Metaspace(replacement=UpperCAmelCase      ,	add_prefix_space=UpperCAmelCase   )

					lowerCAmelCase_      							=			TemplateProcessing(
					    single=F"""$A {self.special_tokens["eos"]["token"]}"""      ,	special_tokens=[(self.special_tokens['''eos''']['''token'''], self.special_tokens['''eos''']['''id'''])]      ,	)

					lowerCAmelCase_      							=			{
					    '''model''': '''SentencePieceUnigram''',
					    '''replacement''': replacement,
					    '''add_prefix_space''': add_prefix_space,
					}

					super().__init__(UpperCAmelCase      ,	UpperCAmelCase   )







				def      lowerCamelCase_     ( self      ,	UpperCAmelCase      ,	UpperCAmelCase = 8000      ,	UpperCAmelCase = True      ,	):

					'''simple docstring'''






					lowerCAmelCase_      							=			trainers.UnigramTrainer(
					    vocab_size=UpperCAmelCase      ,	special_tokens=self.special_tokens_list      ,	show_progress=UpperCAmelCase      ,	)

					if isinstance(UpperCAmelCase      ,	UpperCAmelCase   ):
						lowerCAmelCase_      							=			[files]
					self._tokenizer.train(UpperCAmelCase      ,	trainer=UpperCAmelCase   )

					self.add_unk_id()







				def      lowerCamelCase_     ( self      ,	UpperCAmelCase      ,	UpperCAmelCase = 8000      ,	UpperCAmelCase = True      ,	):

					'''simple docstring'''






					lowerCAmelCase_      							=			trainers.UnigramTrainer(
					    vocab_size=UpperCAmelCase      ,	special_tokens=self.special_tokens_list      ,	show_progress=UpperCAmelCase      ,	)

					self._tokenizer.train_from_iterator(UpperCAmelCase      ,	trainer=UpperCAmelCase   )

					self.add_unk_id()







				def      lowerCamelCase_     ( self   ):

					'''simple docstring'''






					lowerCAmelCase_      							=			json.loads(self._tokenizer.to_str()   )

					lowerCAmelCase_      							=			self.special_tokens['''unk''']['''id''']

					lowerCAmelCase_      							=			Tokenizer.from_str(json.dumps(UpperCAmelCase   )   )



"""simple docstring"""



def      UpperCAmelCase     (       _lowercase :   Optional[Any]	)						-> Tuple:


	"""simple docstring"""




	lowerCAmelCase_      							=			len(_lowercase	)
	lowerCAmelCase_      							=			sum(_lowercase	)

	lowerCAmelCase_      							=			[[False for x in range(s + 1	)] for y in range(n + 1	)]

	for i in range(1			,   n + 1	):
		lowerCAmelCase_      							=			True

	for i in range(1			,   s + 1	):
		lowerCAmelCase_      							=			False

	for i in range(1			,   n + 1	):
		for j in range(1			,   s + 1	):
			lowerCAmelCase_      							=			dp[i][j - 1]

			if arr[i - 1] <= j:
				lowerCAmelCase_      							=			dp[i][j] or dp[i - 1][j - arr[i - 1]]

	for j in range(int(s / 2	)			,   -1			,   -1	):
		if dp[n][j] is True:
			lowerCAmelCase_      							=			s - 2 * j
			break

	return diff