



import json
import os
import shutil
import tempfile
import unittest
from multiprocessing import get_context
from pathlib import Path

import datasets
import numpy as np
from datasets import load_dataset
from parameterized import parameterized

from transformers import AutoProcessor
from transformers.models.wavaveca import WavaVecaCTCTokenizer, WavaVecaFeatureExtractor
from transformers.models.wavaveca.tokenization_wavaveca import VOCAB_FILES_NAMES
from transformers.testing_utils import require_pyctcdecode, require_torch, require_torchaudio, slow
from transformers.utils import FEATURE_EXTRACTOR_NAME, is_pyctcdecode_available, is_torch_available

from ..wavaveca.test_feature_extraction_wavaveca import floats_list


if is_pyctcdecode_available():
							from huggingface_hub import snapshot_download
							from pyctcdecode import BeamSearchDecoderCTC

							from transformers.models.wavaveca_with_lm import WavaVecaProcessorWithLM
							from transformers.models.wavaveca_with_lm.processing_wavaveca_with_lm import WavaVecaDecoderWithLMOutput

if is_torch_available():
							from transformers import WavaVecaForCTC







@require_pyctcdecode
class     __lowerCAmelCase					(    unittest.TestCase		):



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase	 =     '| <pad> <unk> <s> </s> a b c d e f g h i j k'.split()
						_UpperCAmelCase	 =     dict(zip(A				,	range(len(A))))

						_UpperCAmelCase	 =     {
						    'unk_token': '<unk>',
						    'bos_token': '<s>',
						    'eos_token': '</s>',
						}
						_UpperCAmelCase	 =     {
						    'feature_size': 1,
						    'padding_value': 0.0,
						    'sampling_rate': 1_60_00,
						    'return_attention_mask': False,
						    'do_normalize': True,
						}

						_UpperCAmelCase	 =     tempfile.mkdtemp()
						_UpperCAmelCase	 =     os.path.join(self.tmpdirname				,	VOCAB_FILES_NAMES['vocab_file'])
						_UpperCAmelCase	 =     os.path.join(self.tmpdirname				,	A)
						with open(self.vocab_file				,	'w'				,	encoding='utf-8') as fp:
									fp.write(json.dumps(A) + '\n')

						with open(self.feature_extraction_file				,	'w'				,	encoding='utf-8') as fp:
									fp.write(json.dumps(A) + '\n')

						# load decoder from hub
						_UpperCAmelCase	 =     'hf-internal-testing/ngram-beam-search-decoder'



			def 					_lowerCamelCase (		self     :						Optional[int]				,	**A     :						List[Any])     ->					List[Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.add_kwargs_tokens_map.copy()
						kwargs.update(A)
						return WavaVecaCTCTokenizer.from_pretrained(self.tmpdirname				,	**A)



			def 					_lowerCamelCase (		self     :						List[str]				,	**A     :						Tuple)     ->					Tuple:



						"""simple docstring"""






						return WavaVecaFeatureExtractor.from_pretrained(self.tmpdirname				,	**A)



			def 					_lowerCamelCase (		self     :						Union[str, Any]				,	**A     :						List[str])     ->					Optional[int]:



						"""simple docstring"""






						return BeamSearchDecoderCTC.load_from_hf_hub(self.decoder_name				,	**A)



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Any:



						"""simple docstring"""






						shutil.rmtree(self.tmpdirname)



			def 					_lowerCamelCase (		self     :						Any)     ->					Optional[Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						processor.save_pretrained(self.tmpdirname)
						_UpperCAmelCase	 =     WavaVecaProcessorWithLM.from_pretrained(self.tmpdirname)

						# tokenizer
						self.assertEqual(processor.tokenizer.get_vocab()				,	tokenizer.get_vocab())
						self.assertIsInstance(processor.tokenizer				,	A)

						# feature extractor
						self.assertEqual(processor.feature_extractor.to_json_string()				,	feature_extractor.to_json_string())
						self.assertIsInstance(processor.feature_extractor				,	A)

						# decoder
						self.assertEqual(processor.decoder._alphabet.labels				,	decoder._alphabet.labels)
						self.assertEqual(
						    processor.decoder.model_container[decoder._model_key]._unigram_set				,	decoder.model_container[decoder._model_key]._unigram_set				,	)
						self.assertIsInstance(processor.decoder				,	A)



			def 					_lowerCamelCase (		self     :						Union[str, Any])     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(
						    tokenizer=self.get_tokenizer()				,	feature_extractor=self.get_feature_extractor()				,	decoder=self.get_decoder())
						processor.save_pretrained(self.tmpdirname)

						# make sure that error is thrown when decoder alphabet doesn't match
						_UpperCAmelCase	 =     WavaVecaProcessorWithLM.from_pretrained(
						    self.tmpdirname				,	alpha=5.0				,	beta=3.0				,	score_boundary=-7.0				,	unk_score_offset=3)

						# decoder
						self.assertEqual(processor.language_model.alpha				,	5.0)
						self.assertEqual(processor.language_model.beta				,	3.0)
						self.assertEqual(processor.language_model.score_boundary				,	-7.0)
						self.assertEqual(processor.language_model.unk_score_offset				,	3)



			def 					_lowerCamelCase (		self     :						int)     ->					Any:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_tokenizer()
						# add token to trigger raise
						tokenizer.add_tokens(['xx'])
						with self.assertRaisesRegex(A				,	'include'):
									WavaVecaProcessorWithLM(
									    tokenizer=A				,	feature_extractor=self.get_feature_extractor()				,	decoder=self.get_decoder())



			def 					_lowerCamelCase (		self     :						List[str])     ->					Optional[Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						_UpperCAmelCase	 =     floats_list((3, 10_00))

						_UpperCAmelCase	 =     feature_extractor(A				,	return_tensors='np')
						_UpperCAmelCase	 =     processor(A				,	return_tensors='np')

						for key in input_feat_extract.keys():
									self.assertAlmostEqual(input_feat_extract[key].sum()				,	input_processor[key].sum()				,	delta=1E-2)



			def 					_lowerCamelCase (		self     :						List[Any])     ->					List[str]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						_UpperCAmelCase	 =     'This is a test string'

						_UpperCAmelCase	 =     processor(text=A)

						_UpperCAmelCase	 =     tokenizer(A)

						for key in encoded_tok.keys():
									self.assertListEqual(encoded_tok[key]				,	encoded_processor[key])



			def 					_lowerCamelCase (		self     :						Union[str, Any]				,	A     :						Optional[int]=(2, 10, 16)				,	A     :						List[Any]=77)     ->					int:



						"""simple docstring"""






						np.random.seed(A)
						return np.random.rand(*A)



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					List[str]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						_UpperCAmelCase	 =     self._get_dummy_logits(shape=(10, 16)				,	seed=13)

						_UpperCAmelCase	 =     processor.decode(A)

						_UpperCAmelCase	 =     decoder.decode_beams(A)[0]

						self.assertEqual(decoded_decoder[0]				,	decoded_processor.text)
						self.assertEqual('</s> <s> </s>'				,	decoded_processor.text)
						self.assertEqual(decoded_decoder[-2]				,	decoded_processor.logit_score)
						self.assertEqual(decoded_decoder[-1]				,	decoded_processor.lm_score)



			@parameterized.expand([[None], ['fork'], ['spawn']])
			def 					_lowerCamelCase (		self     :						str				,	A     :						Union[str, Any])     ->					Any:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						_UpperCAmelCase	 =     self._get_dummy_logits()

						# note: pool should be instantiated *after* Wav2Vec2ProcessorWithLM.
						#       otherwise, the LM won't be available to the pool's sub-processes.
						# manual logic used to allow parameterized test for both pool=None and pool=Pool(...)
						if pool_context is None:
									_UpperCAmelCase	 =     processor.batch_decode(A)
						else:
									with get_context(A).Pool() as pool:
												_UpperCAmelCase	 =     processor.batch_decode(A				,	A)

						_UpperCAmelCase	 =     list(A)

						with get_context('fork').Pool() as p:
									_UpperCAmelCase	 =     decoder.decode_beams_batch(A				,	A)

						_UpperCAmelCase ,  _UpperCAmelCase ,  _UpperCAmelCase	 =     [], [], []
						for beams in decoded_beams:
									texts_decoder.append(beams[0][0])
									logit_scores_decoder.append(beams[0][-2])
									lm_scores_decoder.append(beams[0][-1])

						self.assertListEqual(A				,	decoded_processor.text)
						self.assertListEqual(['<s> <s> </s>', '<s> <s> <s>']				,	decoded_processor.text)
						self.assertListEqual(A				,	decoded_processor.logit_score)
						self.assertListEqual(A				,	decoded_processor.lm_score)



			def 					_lowerCamelCase (		self     :						Optional[int])     ->					List[str]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						_UpperCAmelCase	 =     self._get_dummy_logits()

						_UpperCAmelCase	 =     15
						_UpperCAmelCase	 =     -2_0.0
						_UpperCAmelCase	 =     -4.0

						_UpperCAmelCase	 =     processor.batch_decode(
						    A				,	beam_width=A				,	beam_prune_logp=A				,	token_min_logp=A				,	)
						_UpperCAmelCase	 =     decoded_processor_out.text

						_UpperCAmelCase	 =     list(A)

						with get_context('fork').Pool() as pool:
									_UpperCAmelCase	 =     decoder.decode_beams_batch(
									    A				,	A				,	beam_width=A				,	beam_prune_logp=A				,	token_min_logp=A				,	)

						_UpperCAmelCase	 =     [d[0][0] for d in decoded_decoder_out]
						_UpperCAmelCase	 =     [d[0][2] for d in decoded_decoder_out]
						_UpperCAmelCase	 =     [d[0][3] for d in decoded_decoder_out]

						self.assertListEqual(A				,	A)
						self.assertListEqual(['</s> <s> <s>', '<s> <s> <s>']				,	A)

						self.assertTrue(np.array_equal(A				,	decoded_processor_out.logit_score))
						self.assertTrue(np.allclose([-2_0.0_5_4, -1_8.4_4_7]				,	A				,	atol=1E-3))

						self.assertTrue(np.array_equal(A				,	decoded_processor_out.lm_score))
						self.assertTrue(np.allclose([-1_5.5_5_4, -1_3.9_4_7_4]				,	A				,	atol=1E-3))



			def 					_lowerCamelCase (		self     :						List[str])     ->					Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						_UpperCAmelCase	 =     self._get_dummy_logits()

						_UpperCAmelCase	 =     2.0
						_UpperCAmelCase	 =     5.0
						_UpperCAmelCase	 =     -2_0.0
						_UpperCAmelCase	 =     True

						_UpperCAmelCase	 =     processor.batch_decode(
						    A				,	alpha=A				,	beta=A				,	unk_score_offset=A				,	lm_score_boundary=A				,	)
						_UpperCAmelCase	 =     decoded_processor_out.text

						_UpperCAmelCase	 =     list(A)
						decoder.reset_params(
						    alpha=A				,	beta=A				,	unk_score_offset=A				,	lm_score_boundary=A				,	)

						with get_context('fork').Pool() as pool:
									_UpperCAmelCase	 =     decoder.decode_beams_batch(
									    A				,	A				,	)

						_UpperCAmelCase	 =     [d[0][0] for d in decoded_decoder_out]

						self.assertListEqual(A				,	A)
						self.assertListEqual(['<s> </s> <s> </s> </s>', '</s> </s> <s> </s> </s>']				,	A)
						_UpperCAmelCase	 =     processor.decoder.model_container[processor.decoder._model_key]
						self.assertEqual(lm_model.alpha				,	2.0)
						self.assertEqual(lm_model.beta				,	5.0)
						self.assertEqual(lm_model.unk_score_offset				,	-2_0.0)
						self.assertEqual(lm_model.score_boundary				,	A)



			def 					_lowerCamelCase (		self     :						Dict)     ->					Union[str, Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     WavaVecaProcessorWithLM.from_pretrained('hf-internal-testing/processor_with_lm')

						_UpperCAmelCase	 =     processor.decoder.model_container[processor.decoder._model_key]
						_UpperCAmelCase	 =     Path(language_model._kenlm_model.path.decode('utf-8')).parent.parent.absolute()

						_UpperCAmelCase	 =     os.listdir(A)
						_UpperCAmelCase	 =     ['alphabet.json', 'language_model']

						downloaded_decoder_files.sort()
						expected_decoder_files.sort()

						# test that only decoder relevant files from
						# https://huggingface.co/hf-internal-testing/processor_with_lm/tree/main
						# are downloaded and none of the rest (e.g. README.md, ...)
						self.assertListEqual(A				,	A)



			def 					_lowerCamelCase (		self     :						str)     ->					str:



						"""simple docstring"""






						_UpperCAmelCase	 =     snapshot_download('hf-internal-testing/processor_with_lm')

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM.from_pretrained(A)

						_UpperCAmelCase	 =     processor.decoder.model_container[processor.decoder._model_key]
						_UpperCAmelCase	 =     Path(language_model._kenlm_model.path.decode('utf-8')).parent.parent.absolute()

						_UpperCAmelCase	 =     os.listdir(A)
						_UpperCAmelCase	 =     os.listdir(A)

						local_decoder_files.sort()
						expected_decoder_files.sort()

						# test that both decoder form hub and local files in cache are the same
						self.assertListEqual(A				,	A)



			def 					_lowerCamelCase (		self     :						Tuple)     ->					Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase	 =     WavaVecaProcessorWithLM.from_pretrained('hf-internal-testing/processor_with_lm')
						_UpperCAmelCase	 =     AutoProcessor.from_pretrained('hf-internal-testing/processor_with_lm')

						_UpperCAmelCase	 =     floats_list((3, 10_00))

						_UpperCAmelCase	 =     processor_wavaveca(A				,	return_tensors='np')
						_UpperCAmelCase	 =     processor_auto(A				,	return_tensors='np')

						for key in input_wavaveca.keys():
									self.assertAlmostEqual(input_wavaveca[key].sum()				,	input_auto[key].sum()				,	delta=1E-2)

						_UpperCAmelCase	 =     self._get_dummy_logits()

						_UpperCAmelCase	 =     processor_wavaveca.batch_decode(A)
						_UpperCAmelCase	 =     processor_auto.batch_decode(A)

						self.assertListEqual(decoded_wavaveca.text				,	decoded_auto.text)



			def 					_lowerCamelCase (		self     :						int)     ->					Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.get_feature_extractor()
						_UpperCAmelCase	 =     self.get_tokenizer()
						_UpperCAmelCase	 =     self.get_decoder()

						_UpperCAmelCase	 =     WavaVecaProcessorWithLM(tokenizer=A				,	feature_extractor=A				,	decoder=A)

						self.assertListEqual(
						    processor.model_input_names				,	feature_extractor.model_input_names				,	msg='`processor` and `feature_extractor` model input names do not match'				,	)



			@staticmethod
			def 					_lowerCamelCase (		A     :						List[str]				,	A     :						List[Any])     ->					int:



						"""simple docstring"""






						_UpperCAmelCase	 =     [d[key] for d in offsets]
						return retrieved_list



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					List[Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     WavaVecaProcessorWithLM.from_pretrained('hf-internal-testing/processor_with_lm')
						_UpperCAmelCase	 =     self._get_dummy_logits()[0]

						_UpperCAmelCase	 =     processor.decode(A				,	output_word_offsets=A)
						# check Wav2Vec2CTCTokenizerOutput keys for word
						self.assertEqual(len(outputs.keys())				,	4)
						self.assertTrue('text' in outputs)
						self.assertTrue('word_offsets' in outputs)
						self.assertTrue(isinstance(A				,	A))

						self.assertEqual(' '.join(self.get_from_offsets(outputs['word_offsets']				,	'word'))				,	outputs.text)
						self.assertListEqual(self.get_from_offsets(outputs['word_offsets']				,	'word')				,	['<s>', '<s>', '</s>'])
						self.assertListEqual(self.get_from_offsets(outputs['word_offsets']				,	'start_offset')				,	[0, 2, 4])
						self.assertListEqual(self.get_from_offsets(outputs['word_offsets']				,	'end_offset')				,	[1, 3, 5])



			def 					_lowerCamelCase (		self     :						Optional[int])     ->					int:



						"""simple docstring"""






						_UpperCAmelCase	 =     WavaVecaProcessorWithLM.from_pretrained('hf-internal-testing/processor_with_lm')
						_UpperCAmelCase	 =     self._get_dummy_logits()

						_UpperCAmelCase	 =     processor.batch_decode(A				,	output_word_offsets=A)

						# check Wav2Vec2CTCTokenizerOutput keys for word
						self.assertEqual(len(outputs.keys())				,	4)
						self.assertTrue('text' in outputs)
						self.assertTrue('word_offsets' in outputs)
						self.assertTrue(isinstance(A				,	A))

						self.assertListEqual(
						    [' '.join(self.get_from_offsets(A				,	'word')) for o in outputs['word_offsets']]				,	outputs.text)
						self.assertListEqual(self.get_from_offsets(outputs['word_offsets'][0]				,	'word')				,	['<s>', '<s>', '</s>'])
						self.assertListEqual(self.get_from_offsets(outputs['word_offsets'][0]				,	'start_offset')				,	[0, 2, 4])
						self.assertListEqual(self.get_from_offsets(outputs['word_offsets'][0]				,	'end_offset')				,	[1, 3, 5])



			@slow
			@require_torch
			@require_torchaudio
			def 					_lowerCamelCase (		self     :						Optional[int])     ->					int:



						"""simple docstring"""






						import torch

						_UpperCAmelCase	 =     load_dataset('common_voice'				,	'en'				,	split='train'				,	streaming=A)
						_UpperCAmelCase	 =     ds.cast_column('audio'				,	datasets.Audio(sampling_rate=1_60_00))
						_UpperCAmelCase	 =     iter(A)
						_UpperCAmelCase	 =     next(A)

						_UpperCAmelCase	 =     AutoProcessor.from_pretrained('patrickvonplaten/wav2vec2-base-100h-with-lm')
						_UpperCAmelCase	 =     WavaVecaForCTC.from_pretrained('patrickvonplaten/wav2vec2-base-100h-with-lm')

						# compare to filename `common_voice_en_100038.mp3` of dataset viewer on https://huggingface.co/datasets/common_voice/viewer/en/train
						_UpperCAmelCase	 =     processor(sample['audio']['array']				,	return_tensors='pt').input_values

						with torch.no_grad():
									_UpperCAmelCase	 =     model(A).logits.cpu().numpy()

						_UpperCAmelCase	 =     processor.decode(logits[0]				,	output_word_offsets=A)

						_UpperCAmelCase	 =     model.config.inputs_to_logits_ratio / processor.feature_extractor.sampling_rate
						_UpperCAmelCase	 =     [
						    {
						        'start_time': d['start_offset'] * time_offset,
						        'end_time': d['end_offset'] * time_offset,
						        'word': d['word'],
						    }
						    for d in output['word_offsets']
						]

						_UpperCAmelCase	 =     'WHY DOES MILISANDRA LOOK LIKE SHE WANTS TO CONSUME JOHN SNOW ON THE RIVER AT THE WALL'

						# output words
						self.assertEqual(' '.join(self.get_from_offsets(A				,	'word'))				,	A)
						self.assertEqual(' '.join(self.get_from_offsets(A				,	'word'))				,	output.text)

						# output times
						_UpperCAmelCase	 =     torch.tensor(self.get_from_offsets(A				,	'start_time'))
						_UpperCAmelCase	 =     torch.tensor(self.get_from_offsets(A				,	'end_time'))

						# fmt: off
						_UpperCAmelCase	 =     torch.tensor([1.4_1_9_9, 1.6_5_9_9, 2.2_5_9_9, 3.0, 3.2_4, 3.5_9_9_9, 3.7_9_9_9, 4.0_9_9_9, 4.2_6, 4.9_4, 5.2_8, 5.6_5_9_9, 5.7_8, 5.9_4, 6.3_2, 6.5_3_9_9, 6.6_5_9_9])
						_UpperCAmelCase	 =     torch.tensor([1.5_3_9_9, 1.8_9_9_9, 2.9, 3.1_6, 3.5_3_9_9, 3.7_2, 4.0_1_9_9, 4.1_7_9_9, 4.7_6, 5.1_5_9_9, 5.5_5_9_9, 5.6_9_9_9, 5.8_6, 6.1_9_9_9, 6.3_8, 6.6_1_9_9, 6.9_4])
						# fmt: on

						self.assertTrue(torch.allclose(A				,	A				,	atol=0.0_1))
						self.assertTrue(torch.allclose(A				,	A				,	atol=0.0_1))





import unittest

from knapsack import knapsack as k







class     __lowerCAmelCase					(    unittest.TestCase		):



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Any:



						"""simple docstring"""






						_UpperCAmelCase	 =     0
						_UpperCAmelCase	 =     [0]
						_UpperCAmelCase	 =     [0]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	0)

						_UpperCAmelCase	 =     [60]
						_UpperCAmelCase	 =     [10]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	0)



			def 					_lowerCamelCase (		self     :						str)     ->					List[str]:



						"""simple docstring"""






						_UpperCAmelCase	 =     3
						_UpperCAmelCase	 =     [1, 2, 3]
						_UpperCAmelCase	 =     [3, 2, 1]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	5)



			def 					_lowerCamelCase (		self     :						Tuple)     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase	 =     50
						_UpperCAmelCase	 =     [60, 1_00, 1_20]
						_UpperCAmelCase	 =     [10, 20, 30]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	2_20)


if __name__ == "__main__":
							unittest.main()
