Count posts within a custom post type and specific taxonomy and terms?

I’m looking to count how many post live within the custom post type called “videos”, but only the ones from the category called “work”.

<?php $count_posts = wp_count_posts('videos'); echo $count_posts->publish; // ?>

How can I adjust the above code to accomplish this?

Thanks!

An alternative solution using WP_Query would be:

$args = array(
  'cat' => 4,
  'post_type' => 'videos'
);
$the_query = new WP_Query( $args );
echo $the_query->found_posts;